j
)}
min{
T
(v4
),
T
(v5
),
T
(v6
)}
T
(v4
)
T
(v5
)
5,
所以有， p(v4 ) 5, p(v5 ) 5
（6） T (v6 ) min[T (v6 ), P(v4 ) l46, P(v5 ) l56 ] min[, 5 4,5 2] 7
X={1,2,4}, p2=2
ppt课件
13
X={1,2,4}
p1=0
p2=2
2
6
1
2
3
1
10
p4=1
5
9
3
4
7
5
6
5
2
3
4
6
7
4
p6=3
8 8
min {d16,d23,d25,d47}=min {0+3,2+6,2+5,1+2}=min {3,8,7,3}=3
X={1,2,4,6}, p6=3
ppt课件
P(v1) 0
T (vi ) (i 2,3,,6)
（2） T (v2 ) min[ T (v2 ), P(v1) l12 ] min[ , 0 3] 3
T (v3 ) min[ T (v3 ), P(v1 ) l13 ] min[ , 0 5] 5
最短路问题
ppt课件
1
一、问题的提法及应用背景
（1）问题的提法——寻求网络中两点间 的最短路就是寻求连接这两个点的边的 总权数最小的通路。（注意：在有向图 中，通路——开的初等链中所有的弧应 是首尾相连的。）
