5-2,最 短 路 问 题
一、问题的提法及应用背景
（ 1） 问题的提法 —— 寻求网络中两点间
的最短路就是寻求连接这两个点的边的
总权数为最小的通路 。 （ 注意：在有向
图中, 通路 —— 开的初等链 中所有的弧
应是 首尾相连 的 。 ）
（ 2） 应用背景 —— 管道铺设, 线路安排,
厂区布局, 设备更新等 。
二、最短路算法：
1,D氏标号法（ Dijkstra）
（ 1）求解思路 —— 从始点出发，逐步 顺序
地向外探寻, 每向外延伸一步都要求是 最
短的。
（ 2）使用条件 —— 网络中 所有的弧权 均
非负,即 。
0?ijw
（ 3）选用符号的意义,
① 标号 P（固定标号或永久性标号）
—— 从始点到该标号点的最短路权 。
② 标号 T（临时性标号）
—— 从始点到该标号点的最短路权 上界 。
（ 4） 计算步骤及例,
? ?jj lvpvT 11 )(),(m i n ?
jv
s sv
j ?
jv
Avv j ?),( 1 jv
第二步,考虑满足条件
① 的所有点 ；
② 具有 T 标号, 即, 为 T
标号点集 。
修改 的 T标号为, 并
将结果仍记为 T(vj)
0)( 1 ?vp 第一步,始点标上固定标号,其余各
点标临时性标号 T(vj)=?,j?1;
第三步,若网络图中已无 T标号点, 停止
计算 。 否则,令,
然后 将 的 T 标号改成 P 标号, 转入第
二步 。
此时, 要注意将第二步中的 改为 。
1v
0jv
? ?)()( m in0 j
sv
j vTvT
j ?
?
0jv
例 5-3 用狄克斯拉算法
求解图 5-1所示最短路问题。
4
v1
v2
v3
v4
v6
v5
v7
2
2
5
6
1
4
1
3
4
1
2
图 5-1 例 5-3网络图
解：先将图 5-1的网络用矩阵形式表示出来,
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
???
???
?
??
??
????
?
0214
2013
1046
414014
31025
64202
520
7
6
5
4
3
2
1
V
V
V
V
V
V
V
D
1v 2v 3v 4v 5v 6v 7v
步骤 考察点 T标号点集 标 号 （ 表 P标号 ）
1 v1 {v2,…, v7}
v1 v2 v3 v4 v5 v6 v7
0 - - - - - -
0+2 0+5
2 5 - - - -
2
3
4
5
6
v2
v3
v4
v5
v6
{v3,…, v7}
{v4,…, v7}
{v5,v6,v7}
{v5,v7}
2+2 2+4 2+6
4 6 8 - -
4+1 4+3
5 8 7 -
5+4 5+1 5+4
8 6 9
6+2
8 8
{v7} 8+1
8
反向追踪, 得到最优路线：
v1 v2 v3 v4 v6 v7
v5
讨论,若先把 v7的标号改为永久性标号,
该怎麽继续作下去？
5
6
v6
v7
{v5,v7}
{v5}
v1 v2 v3 v4 v5 v6 v7
6+2
8 8
8+1
8
8 6 9
反向追踪, 得到相同的最优路线 。
在得到从起点到终点的最短路长的同时, 还
能得到什麽附加信息？
（ 5） D氏标号法（ Dijkstra） 的特点
（获得的附加信息）：
1v
能得到从 （ 起点 ） 到各点的 最短
路线和最短路长 。
2,列表法（ Ford算法）
求从点 到任何一点 （ ）
的最短路。
（ 1）使用条件 — 没有负回路
（ 2）步骤：
① 令,,其中 为起点
到 的弧（ ）的权；
1v
1v jv
Nj,,3,2 ??
? ?
jj wd 1
1 ? Nj,,3,2 ??
jw1
jv jvv,1
③ 当迭代到第 步，有 时，收敛；
就是从起点 到各点的最短路权；
? ? ? ?dd l
j
l
j
1?? l
??dl
j 1v
④ 反向追踪求出最短路线。
其中, 表示从起点 到点 至多含
k-1个中间点的最短路权；
? ?dk
j jv 1v
? ? ? ?? ?
ij
k
ji
k
j wdd ??
? 1m in Nj,,3,2 ??
② 用下列递推公式进行迭代：
例 5-4：计算下图中从 vs到 vt的最短路
线和最短路长
v2
-1
vs
v1
v3
vt
4
-1
1
1
3
2
6
-2
vs
v1
v2
v3
vt
0
---
-1
---
---
4
0
---
---
-1
1
-2
0
---
---
---
6
3
0
---
---
1
---
2
0
0
4
1
---
---
0
4
1
4
5
0
4
1
4
5
vs v1 v2 v3 vt )1(jd )2(jd )3(jd
ts vvv ?? 1
最短路线为, 最短路权为 5。
反向追踪寻找最短路线, 得：
=min（ 0+4,4+0,1+ -,- + -,- +（ -1） ）
=4
依此类推 …
计算过程详示：
tsjwd jj,3,2,1,1)1( ??
)(m i n )1()2( isi
is
wdd ??
=min（ 0+0,4+ -,1+（ -1）, - + -,- + -）
=0
)(m i n 1)1()2(1 iii wdd ??
v2
vs v
s v1
…
…
…
…
反向追踪过程：
寻求一点 vk，使,本题中 vk
即为 v1，所以找到弧（ v1,vt）；
再寻求一点 vi,使,这里，
vi即为 vs,所以 找到弧（ vs,v1）；
于是得最短路线
ltktlk dwd ??? 1
lili dwd 411 ???
ts vvv ?? 1
② 优点, 可以在有负权的情况下，寻求 从
起点到各个点 的最短路线和最短路长。
3,海斯算法
（ 1） 算法思想：
利用 vi到 vj的一步距离求出 vi到 vj
的两步距离,再由两步距离求出四步
距离,经有限步迭代即可求得 vi到 vj的
最短路线和最短距离 。
（ 2） 算法步骤：
?令
则 是指 vi到 vj的一步距离；
nild ijij,,2,1)0( ???
)0(ijd
?当 已知时,令)1( ?m
ijd
}{m in )1()1(
~1
)( ??
?
?? mkjmik
nk
m
ij ddd
则 当 m=1时, 是 vi到 vj走两步的最小距离；
当 m=2时, 是 vi 到 vj走四步的最小距离；
一般, 是 vi 到 vj 走 2m步的最小距离；)(m
ijd
)2(ijd
)1(ijd
?当对所有 I,j有, 时,则
)1()( ?? mijmij dd
)(mijd
是 vi到 vj的最短距离 。
由于最短路线上最多有 n-1条边, 因此, 当
2m n-1时,就是最短距离 。?
)(m
ijd
（ 3） 算法举例：
例 5-5 用海斯算法求下面的网络图中从 v1到 v6
的最短距离和最短路线 。
v1
v2
v3
v4
v5
v6
2
6
8
3
9
5
3
3
1
写出其距离矩阵
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
??
??
?
?
???
??
013
1039
3058
35036
98302
620
654321
)0(
vvvvvv
LD
第一轮迭代：
按照迭代公式进
行计算, 求得矩
阵 D（ 1） =(dij (1))
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
013410
104369
3405810
435035
1068302
910520
654321
6
5
4
3
2
1
)1(
vvvvvv
v
v
v
v
v
v
D
第一行计算示例：
取自第 1列
（ 第 1行 +第 2列 ）
2
},9,8,36,02,20m i n {
},,
,,,m i n {
}{m i n
)0(
62
)0(
16
)0(
52
)0(
15
)0(
42
)0(
14
)0(
32
)0(
13
)0(
22
)0(
12
)0(
12
)0(
11
)0(
2
)0(
1
)1(
12
?
???????????
???
????
??
dddddd
dddddd
ddd
kk
k
5
},3,5,06,32,60m i n {
},,
,,,m i n {
}{m i n
)0(
63
)0(
16
)0(
53
)0(
15
)0(
43
)0(
14
)0(
33
)0(
13
)0(
23
)0(
12
)0(
13
)0(
11
)0(
3
)0(
1
)1(
13
?
???????????
???
????
??
dddddd
dddddd
ddd
kk
k
取自第 2列
（ 第 1行 +第 3列 ）
10
}3,,0,56,82,0m i n {
},,
,,,m i n {
}{m i n
)0(
64
)0(
16
)0(
54
)0(
15
)0(
44
)0(
14
)0(
34
)0(
13
)0(
24
)0(
12
)0(
14
)0(
11
)0(
4
)0(
1
)1(
14
?
????????????
???
????
??
dddddd
dddddd
ddd
kk
k
取自第 2列
（ 第 1行 +第 4列 ）
9
}1,0,,36,92,0m i n {
},,
,,,m i n {
}{m i n
)0(
65
)0(
16
)0(
55
)0(
15
)0(
45
)0(
14
)0(
35
)0(
13
)0(
25
)0(
12
)0(
15
)0(
11
)0(
5
)0(
1
)1(
15
?
????????????
???
????
??
dddddd
dddddd
ddd
kk
k
取自第 3列
（ 第 1行 +第 5列 ）
??
?????????????
???
????
??
}0,1,3,6,2,0m i n {
},,
,,,m i n {
}{m i n
)0(
66
)0(
16
)0(
56
)0(
15
)0(
46
)0(
14
)0(
36
)0(
13
)0(
26
)0(
12
)0(
16
)0(
11
)0(
6
)0(
1
)1(
16
dddddd
dddddd
ddd
kk
k
（ 第 1行 +第 6列 ）
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
65455
556333
464332
533322
533221
32211
?相应的中间点矩阵：
第二轮迭代,由 D（ 1） 按公式迭代得 D(2)
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
013479
104368
3405810
435035
768302
9810520
654321
)2(
vvvvvv
D
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
654333
554322
444321
333321
322221
321111
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
654321
554321
444321
333321
222221
111111
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
013479
104368
3405810
435035
768302
9810520
654321
)3(
vvvvvv
D
第三轮迭代,由 D(2)按公式迭代得 D(3)
由于 D(2) =D(3),故 D(3)中的元素就是 vi到 vj的
最短距离,D(3)称为最短距离矩阵 。
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
65455
556333
464332
533322
533221
32211
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
654333
554322
444321
333321
322221
321111
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
654321
554321
444321
333321
222221
111111
611 vvv ??
中转点
631 vvv ??
中转点
653
321
vvv
vvv
??
??
于是, 得到由 v1到 v6的最短
路线为：
65321 vvvvv ????
（ 4） 海斯算法的特点
? 能求出网络中的点 两两之间的最短
距离；
? 算法效率较高, m次迭代即可完成
计算；
? 适用条件 —— 无负回路的任意网络；
第九次作业
P218~P219：
5-2,5-3（只要求建模）
一、问题的提法及应用背景
（ 1） 问题的提法 —— 寻求网络中两点间
的最短路就是寻求连接这两个点的边的
总权数为最小的通路 。 （ 注意：在有向
图中, 通路 —— 开的初等链 中所有的弧
应是 首尾相连 的 。 ）
（ 2） 应用背景 —— 管道铺设, 线路安排,
厂区布局, 设备更新等 。
二、最短路算法：
1,D氏标号法（ Dijkstra）
（ 1）求解思路 —— 从始点出发，逐步 顺序
地向外探寻, 每向外延伸一步都要求是 最
短的。
（ 2）使用条件 —— 网络中 所有的弧权 均
非负,即 。
0?ijw
（ 3）选用符号的意义,
① 标号 P（固定标号或永久性标号）
—— 从始点到该标号点的最短路权 。
② 标号 T（临时性标号）
—— 从始点到该标号点的最短路权 上界 。
（ 4） 计算步骤及例,
? ?jj lvpvT 11 )(),(m i n ?
jv
s sv
j ?
jv
Avv j ?),( 1 jv
第二步,考虑满足条件
① 的所有点 ；
② 具有 T 标号, 即, 为 T
标号点集 。
修改 的 T标号为, 并
将结果仍记为 T(vj)
0)( 1 ?vp 第一步,始点标上固定标号,其余各
点标临时性标号 T(vj)=?,j?1;
第三步,若网络图中已无 T标号点, 停止
计算 。 否则,令,
然后 将 的 T 标号改成 P 标号, 转入第
二步 。
此时, 要注意将第二步中的 改为 。
1v
0jv
? ?)()( m in0 j
sv
j vTvT
j ?
?
0jv
例 5-3 用狄克斯拉算法
求解图 5-1所示最短路问题。
4
v1
v2
v3
v4
v6
v5
v7
2
2
5
6
1
4
1
3
4
1
2
图 5-1 例 5-3网络图
解：先将图 5-1的网络用矩阵形式表示出来,
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
???
???
?
??
??
????
?
0214
2013
1046
414014
31025
64202
520
7
6
5
4
3
2
1
V
V
V
V
V
V
V
D
1v 2v 3v 4v 5v 6v 7v
步骤 考察点 T标号点集 标 号 （ 表 P标号 ）
1 v1 {v2,…, v7}
v1 v2 v3 v4 v5 v6 v7
0 - - - - - -
0+2 0+5
2 5 - - - -
2
3
4
5
6
v2
v3
v4
v5
v6
{v3,…, v7}
{v4,…, v7}
{v5,v6,v7}
{v5,v7}
2+2 2+4 2+6
4 6 8 - -
4+1 4+3
5 8 7 -
5+4 5+1 5+4
8 6 9
6+2
8 8
{v7} 8+1
8
反向追踪, 得到最优路线：
v1 v2 v3 v4 v6 v7
v5
讨论,若先把 v7的标号改为永久性标号,
该怎麽继续作下去？
5
6
v6
v7
{v5,v7}
{v5}
v1 v2 v3 v4 v5 v6 v7
6+2
8 8
8+1
8
8 6 9
反向追踪, 得到相同的最优路线 。
在得到从起点到终点的最短路长的同时, 还
能得到什麽附加信息？
（ 5） D氏标号法（ Dijkstra） 的特点
（获得的附加信息）：
1v
能得到从 （ 起点 ） 到各点的 最短
路线和最短路长 。
2,列表法（ Ford算法）
求从点 到任何一点 （ ）
的最短路。
（ 1）使用条件 — 没有负回路
（ 2）步骤：
① 令,,其中 为起点
到 的弧（ ）的权；
1v
1v jv
Nj,,3,2 ??
? ?
jj wd 1
1 ? Nj,,3,2 ??
jw1
jv jvv,1
③ 当迭代到第 步，有 时，收敛；
就是从起点 到各点的最短路权；
? ? ? ?dd l
j
l
j
1?? l
??dl
j 1v
④ 反向追踪求出最短路线。
其中, 表示从起点 到点 至多含
k-1个中间点的最短路权；
? ?dk
j jv 1v
? ? ? ?? ?
ij
k
ji
k
j wdd ??
? 1m in Nj,,3,2 ??
② 用下列递推公式进行迭代：
例 5-4：计算下图中从 vs到 vt的最短路
线和最短路长
v2
-1
vs
v1
v3
vt
4
-1
1
1
3
2
6
-2
vs
v1
v2
v3
vt
0
---
-1
---
---
4
0
---
---
-1
1
-2
0
---
---
---
6
3
0
---
---
1
---
2
0
0
4
1
---
---
0
4
1
4
5
0
4
1
4
5
vs v1 v2 v3 vt )1(jd )2(jd )3(jd
ts vvv ?? 1
最短路线为, 最短路权为 5。
反向追踪寻找最短路线, 得：
=min（ 0+4,4+0,1+ -,- + -,- +（ -1） ）
=4
依此类推 …
计算过程详示：
tsjwd jj,3,2,1,1)1( ??
)(m i n )1()2( isi
is
wdd ??
=min（ 0+0,4+ -,1+（ -1）, - + -,- + -）
=0
)(m i n 1)1()2(1 iii wdd ??
v2
vs v
s v1
…
…
…
…
反向追踪过程：
寻求一点 vk，使,本题中 vk
即为 v1，所以找到弧（ v1,vt）；
再寻求一点 vi,使,这里，
vi即为 vs,所以 找到弧（ vs,v1）；
于是得最短路线
ltktlk dwd ??? 1
lili dwd 411 ???
ts vvv ?? 1
② 优点, 可以在有负权的情况下，寻求 从
起点到各个点 的最短路线和最短路长。
3,海斯算法
（ 1） 算法思想：
利用 vi到 vj的一步距离求出 vi到 vj
的两步距离,再由两步距离求出四步
距离,经有限步迭代即可求得 vi到 vj的
最短路线和最短距离 。
（ 2） 算法步骤：
?令
则 是指 vi到 vj的一步距离；
nild ijij,,2,1)0( ???
)0(ijd
?当 已知时,令)1( ?m
ijd
}{m in )1()1(
~1
)( ??
?
?? mkjmik
nk
m
ij ddd
则 当 m=1时, 是 vi到 vj走两步的最小距离；
当 m=2时, 是 vi 到 vj走四步的最小距离；
一般, 是 vi 到 vj 走 2m步的最小距离；)(m
ijd
)2(ijd
)1(ijd
?当对所有 I,j有, 时,则
)1()( ?? mijmij dd
)(mijd
是 vi到 vj的最短距离 。
由于最短路线上最多有 n-1条边, 因此, 当
2m n-1时,就是最短距离 。?
)(m
ijd
（ 3） 算法举例：
例 5-5 用海斯算法求下面的网络图中从 v1到 v6
的最短距离和最短路线 。
v1
v2
v3
v4
v5
v6
2
6
8
3
9
5
3
3
1
写出其距离矩阵
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
??
??
?
?
???
??
013
1039
3058
35036
98302
620
654321
)0(
vvvvvv
LD
第一轮迭代：
按照迭代公式进
行计算, 求得矩
阵 D（ 1） =(dij (1))
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
013410
104369
3405810
435035
1068302
910520
654321
6
5
4
3
2
1
)1(
vvvvvv
v
v
v
v
v
v
D
第一行计算示例：
取自第 1列
（ 第 1行 +第 2列 ）
2
},9,8,36,02,20m i n {
},,
,,,m i n {
}{m i n
)0(
62
)0(
16
)0(
52
)0(
15
)0(
42
)0(
14
)0(
32
)0(
13
)0(
22
)0(
12
)0(
12
)0(
11
)0(
2
)0(
1
)1(
12
?
???????????
???
????
??
dddddd
dddddd
ddd
kk
k
5
},3,5,06,32,60m i n {
},,
,,,m i n {
}{m i n
)0(
63
)0(
16
)0(
53
)0(
15
)0(
43
)0(
14
)0(
33
)0(
13
)0(
23
)0(
12
)0(
13
)0(
11
)0(
3
)0(
1
)1(
13
?
???????????
???
????
??
dddddd
dddddd
ddd
kk
k
取自第 2列
（ 第 1行 +第 3列 ）
10
}3,,0,56,82,0m i n {
},,
,,,m i n {
}{m i n
)0(
64
)0(
16
)0(
54
)0(
15
)0(
44
)0(
14
)0(
34
)0(
13
)0(
24
)0(
12
)0(
14
)0(
11
)0(
4
)0(
1
)1(
14
?
????????????
???
????
??
dddddd
dddddd
ddd
kk
k
取自第 2列
（ 第 1行 +第 4列 ）
9
}1,0,,36,92,0m i n {
},,
,,,m i n {
}{m i n
)0(
65
)0(
16
)0(
55
)0(
15
)0(
45
)0(
14
)0(
35
)0(
13
)0(
25
)0(
12
)0(
15
)0(
11
)0(
5
)0(
1
)1(
15
?
????????????
???
????
??
dddddd
dddddd
ddd
kk
k
取自第 3列
（ 第 1行 +第 5列 ）
??
?????????????
???
????
??
}0,1,3,6,2,0m i n {
},,
,,,m i n {
}{m i n
)0(
66
)0(
16
)0(
56
)0(
15
)0(
46
)0(
14
)0(
36
)0(
13
)0(
26
)0(
12
)0(
16
)0(
11
)0(
6
)0(
1
)1(
16
dddddd
dddddd
ddd
kk
k
（ 第 1行 +第 6列 ）
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
65455
556333
464332
533322
533221
32211
?相应的中间点矩阵：
第二轮迭代,由 D（ 1） 按公式迭代得 D(2)
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
013479
104368
3405810
435035
768302
9810520
654321
)2(
vvvvvv
D
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
654333
554322
444321
333321
322221
321111
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
654321
554321
444321
333321
222221
111111
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
013479
104368
3405810
435035
768302
9810520
654321
)3(
vvvvvv
D
第三轮迭代,由 D(2)按公式迭代得 D(3)
由于 D(2) =D(3),故 D(3)中的元素就是 vi到 vj的
最短距离,D(3)称为最短距离矩阵 。
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
65455
556333
464332
533322
533221
32211
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
654333
554322
444321
333321
322221
321111
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
654321
554321
444321
333321
222221
111111
611 vvv ??
中转点
631 vvv ??
中转点
653
321
vvv
vvv
??
??
于是, 得到由 v1到 v6的最短
路线为：
65321 vvvvv ????
（ 4） 海斯算法的特点
? 能求出网络中的点 两两之间的最短
距离；
? 算法效率较高, m次迭代即可完成
计算；
? 适用条件 —— 无负回路的任意网络；
第九次作业
P218~P219：
5-2,5-3（只要求建模）
