2
3
1
10
p4=1
5
9
3
4
7
5
6
5
2
3
4
6
7
8
4
8
p6=3
p7=3
min {d23,d25,c47,d67}=min {2+6,2+5,1+2,3+4}=min {8,7,3,7}=3
X={1,2,4,6,7}, p7=3
X={1,2,4,6,7}
p1=0
p2=2
2
6
1
2
3
1
10
p4=1
5
9
p5=6
——从始点到该标号点的最短路权
② T 标号（Temporary临时性标号）
——从始点到该标号点的最短路权上界
（4） 计算步骤及例子：
第一步：给起始点v1标上固定标号p(v1)0 ,
其余各点标临时性标号 T(vj)=, j1;
第二步：考虑满足如下条件的所有点 v j ①与 v1相邻的点，即(v1, v j ) A ;
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
X={1,2,4,6}
p1=0
p2=2
2
6
1
m v j s{ T ( v ij)n } m T ( v i4 )n T ( ,v 5 ) { T ( ,v 6 ) } T ( v 4 ) T ( v 5 ) 5 , 所p 以 ( v 4 ) 5 ,p 有 ( v 5 ) 5，
（6） T(v6)mT i(n v6),[P (v4)l4,6P (v5)l5]6 m in, 5[4,52]7
② v j 具有T 标号，即v j s ，s 为T 标号点集.
修改 v j 的T标号为 miTn (vj{ ),p(v1)l1j}，并将结
果仍记为T(vj)。= l1j
❖若网络图中已无满足此条件的T标号点，停止计算。
第三步： 令T(vj0)m vjsi{T n(vj)}, 然后将 v j0 的
T 标号改成P 标号，转入第二步。此时，要
m vj s{ T i(v n j) }mT i(v n 6){ }7 , 所以 p (v6)有 7 ，
反向追踪得v1到v6的最短路为：v1 v2 v5 v6
求从1到8的最短路径
2
6
1
2
3
1
10
5
9
3
4
7
5
6
5
2
3
4
6
7
4
8 8
X={1}
p1=0
2
6
1
2
3
1
10
p4=1
5
9
3
4
7
5
6
5
2
3
4
6
例一、
用Dijkstra算法求下图从v1到v6的最短路。
v2 2
v4
3
v1
1
4
22
v6
5 v3 4
2 v5
（4）T ( v 3 ) m T ( v 3 ) i ,P ( n v 2 ) l [ 2 ] 3 m 5 ,3 i1 ] n 4[
T ( v 4 ) m T ( v 4 ) , P i ( v 2 n ) l 2 ] [ 4 m , 3 i 2 ] n 5[ T ( v 5 ) m T ( v 5 ) i ,P ( n v 2 ) l 2 [ ] 5 m ,3 i 2 n ] 5 [
注意将第二步中的 v 1 改为v j0 。
例一、
用Dijkstra算法求下图从v1到v6的最短路。
v2 2
v4
3
v1
1
4
22
v6
5 v3 42 v5 Nhomakorabea解 （1）首先给v1以P标号，给其余所有点T标号。
P(v1)0 T (v i) (i 2 ,3 , ,6 )
（2） T ( v 2 ) m T ( v 2 ) , i P ( v 1 n ) l 1 ] [ 2 m ,0 i 3 ] n 3[
最短路问题
一、问题的提法及应用背景
（1）问题的提法——寻求网络中两点间 的最短路就是寻求连接这两个点的边的 总权数最小的通路。（注意：在有向图 中，通路——开的初等链中所有的弧应 是首尾相连的。）
（2）应用背景——管道铺设、线路安排、 厂区布局、设备更新等。
二、最短路算法
1． D氏标号法（Dijkstra）；边权非负 2. 列表法（福德法）；有负权，无负回路
m vj s{T i(n vj)} mT i(n v3){ T ,(v4)T ,(v5)T ,(v6)} T(v3)4, 所以 p(v3 有 )4，
v2 2
3
v1
1
2
v4
4
2
v6
5 v3 4
2 v5
（5）T ( v 5 ) m T ( v 5 ) i ,P n ( v 3 ) l [ 3 ] 5 m 5 ,4 i4 ] n 5[
T ( v 3 ) m T ( v 3 ) i ,P ( n v 1 ) l 1 [ ] 3 m ,0 i 5 n ] 5 [
m vj s{ T i(v n j) }mT i(v n 2)T { ,(v3)T ,(v4)T ,(v5)T ,(v6)} T (v2)3 , 所以 p (v2)有 3 ，
6
5
2
3
4
6
7
8
4
8
p6=3
p7=3
min {d23,d53,d58,d78}=min {2+6,6+9,6+4,3+8}=min {8,15,10,11}=8
3
4
7
5
6
5
2
3
4
6
7
8
4
8
p6=3
p7=3
min {d23,d25,d75,d78}=min {2+6,2+5,3+3,3+8}=min {8,7,6,11}=6
X={1,2,4,5,6,7}, p5=6
X={1,2,4,6,7}
p1=0 1
3
p2=2 2
2
1
10
p4=1
4
7
6
5
9
p5=6
5
p3=8 3
v2
6
v5
2
4
1
4
v1
2
5
v4
1
1
4
v7
2
v3
3
v6
1．D氏标号法（Dijkstra）
（1）求解思路——从始点出发，逐步顺序 地向外探寻，每向外延伸一步都要求是最 短的。
（2）使用条件——网络中所有的弧权均 非负，即 lij 0 。
（3）选用符号的意义：
① P 标号（Permanent固定/永久性标号）
7
4
8 8
min {d12,d14,d16}=min {0+2,0+1,0+3}=min {2,1,3}=1 X={1,4}, p4=1
X={1,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
8 8
min {d12,d16,d42,d47}=min {0+2,0+3,1+10,1+2}=min {2,3,11,3}=2 X={1,2,4}, p2=2