5
3 10
1 2
2
v1
2
8
4 2 4
v3
6
v5
D ( 0) D
最短路问题在图论应用中处于很重要的地位， 下面举两个实际应用的例子。 例1 设备更新问题 某工厂使用一台设备，每年年初工厂要作出决定： 继续使 用旧的还是购买新的？如果继续使用旧的， 要付维修费；若要购买 一套新的，要付购买费。试 确定一个5年计划，使总支出最小. 若已知设备在各年的购买费，及不同机器役龄时的 残值与维修费，如表所示.
给 (v1 , v5 ) 划成彩线。
59 40 28 30
21
v1 (0)
①
12
v2 (12)
②
19 13
v3 (19)14 20
v4 (28) 15
29
④
15 v5 (40)
22
⑤
v6
③
41
k16 , k26 , k36 , k46 , k56 } ⑹ min{ min{ 59,53,49,50,55} 49
min{ k24 , k25 , k34 , k35} min{ 9,8,10,13} 8
① 给 (v2 , v5 ) 划成粗线。
② 给 v5 标号（8）。 ③ 划第4个弧。
v2 (4)
4
5
4
v4(9)
7
9
5
v6
1
v1 (0)
①
②
6
③
4
5
v8
1
v3(6)
7
v5 (8)
④
6
⑤
v7
5）接着往下考察，有四条路可走：(v2 , v4 ), (v3 , v4 ), (v5 , v6 ), (v5 , v7 ). 可选择的最短路为
vs , vt 为图中任意两点，求一条道路 ，使它是从 v s 到
vt 的所有路中总权最小的路。即：
L( )
最小。
( vi , v j )
l
ij
最短路算法中1959年由 Dijkstra （狄克斯特洛）提出的
算法被公认为是目前最好的方法，我们称之为 Dijkstra 算 法。下面通过例子来说明此法的基本思想。 条件：所有的权数 lij 0 思路：逐步探寻。
年底）。
59 40 28 30
21
v1
12
v2
19 13
20
v3 14
29
v4 15
22
v5
15
v6
41
边 (vi , v j ) 上的数字表示第i年初购进设备，一直使用到第j年 初所需支付的购买费、维修的全部费用（可由表8-2计算得
到）。
这样设备更新问题就变为：求从 v1 到 v6 的最短路问题.
59 40 28 30
21
v1 (0)
①
12
v2 (12)
②
19 13
v3 (19)14 20
v4 (28) 15
29
④
15 v5 (40)
22
⑤
v6
③
41
⑸
min{k15 , k16 , k25 , k26 , k35 , k36 , k45 , k46 } min{40,59,41,43,35,49,43,50} 40
min{ k24 , k34 , k56 , k57 } min{ 9,10,13,14} 9
① 给 (v2 , v4 ) 划成粗线。 ② 给 v4 标号（9）。 ③ 划第5个弧。
v2 (4)
4
5
4
v4(9)
7
9
5
v6 (13)
1
v1 (0)
①
②
6
③
4
5
v8
1
v3(6)
7
v5 (8)
④
6
⑤ ⑥
① 同时给 (v5 , v7 ), 划成粗线。
② 分别给
标号（14）。
v2 (4)
4
5
4
v4(9)
7
9
5
v6 (13)
1
v1 (0)
6
4
5
v8 (14)
1
v3(6)
7
v5 (8)
6
v7 (14)
最后，从 v8 逆寻粗线到 v1 ，得最短路：
v1 v2 v5 v6 v8
长度为14。
最短路问题的两个应用
给 (v4 , v6 )划线。
v3 (20)
20 25
60 20
v4 (0)
18
30
v5
v1
30
v2 15 v6 (18) 15
v7
⑶
min{ k43 , k45 , k63 , k62 , k67 } min{ 20,30,43,33,33} 20
给 v3 标号20。 给 (v4 , v3 ) 划线。
lij 当 (vi , v j ) E d ij 其他
算法基本步骤为： ⑴ 输入权矩阵
D(0) D.
v2
例
v1 v2 v3 v4 v5 v1 0 v2 5 v3 2 v4 2 v5
0 10 2 3 0 2 8 6 0 4 2 4 4 0 5 1 2
v3 (20)
20 25
15
60 20
v4 (0)
18
30
v5 (30)
v1 (60)
30
v2 (33)
v6 (18) 15
v7 (33)
⑹
min{ k21} min{ 63} 63
给 v1 标号63。 给 (v2 , v1 ) 划成彩线。 其它计算结果见下表：
小区号
v1 v2 v3 v4 v5 v6 v7
项目 购买费 维修费 残值
第 1年 11 5 4
第 2年 12 1-2 6 3
第 3年 13 2-3 8 2
第 4年 14 3-4 11 1
第 5年 14 4-5 18 0
机器役龄 0-1
解：把这个问题化为最短路问题。 用点 vi 表示第i年初购进一台新设备，虚设一个点 v6 ，表示第 5年底。 边 表示第i年购进的设备一直使用到第j年初（即第j-1
给 (v3 , v6 ) 划成彩线。 计算结果：最短路
v1 v3 v6
59 40 28 30
21
v1 (0)
①
12
②
v2 (12)
19 13
v3 (19)14 20
v4 (28) 15
29
④
15 v5 (40)
22
⑤
v6
③
41
最短路路长为49。 即：在第一年、第三年初各购买一台新设备为最优决策。 这时5年的总费用为49。
v2 (4)
4
5
4
v4
7
9
5
v6
1
v1 (0)
①
②
6
4
5
1
v8
v3(6)
③
7
v5
6
v7
3）接着往下考察，有三条路可走：(v1 , v3 ), (v2 , v4 ), (v2 , v5 ).
可选择的最短路为
min{ k13 , k24 , k25} min{ l13 , l12 d24 , l12 d25} min{ 6,4 5,4 4} 6
v3 (20)
20 25
15
60 20
v4 (0)
18
30
v5 (30)
v1
30
v2 (33)
v6 k32 , k62 , k67 } min{ 30,80,40,33,33} 30
给 v5 标号30。 给 (v4 , v5 ) 划线。
60 30 40 33 63 15 0
48
63
由于 D(v6 ) 48 最小，所以医院应建在 v6 ，此时离医院最 远的小区 v5 距离为48。
Floyd （佛洛伊德）算法 这里介绍得Floyd（1962年）可直接求出网络中任意两
点间的最短路。
令网络中的权矩阵为 D (dij )nn , 其中
2）从 v1 出发，只有两条路可走 (v1 , v2 ), (v1 , v3 ) ，其距离为
l12 4, l13 6.
v2 (4)
4
5
4
v4
7
9
5
v6
1
v1 (0)
①
②
6
4
5
v8
1
v3
7
v5
6
v7
可能最短路为
min{ k12 , k13} min{ l12 , l13} min{ 4,6} 4
v5
v4
18
30
v2 15
v6
15
如
v7
D(v1 ) max{ d1 , d2 ,d7 }
再求
min{D(v1 ), D(v2 ),, D(v7 )}
即为所求。 比如求 D(v4 )
v3
20 25 60 20
v4 (0)
18
30
v5
v1
30
v2 15 v6 (18) 15
v7
⑴
v4(0)
k43 , k45 , k46 } min{ 20,30,18} 18 ⑵ min{
v3 (20)
20 25
15
60 20
v4 (0)
18
30
v5 (30)
v1
30