Ch6 Graph and Network
2012年12月31日星期一 Page 14 of 14
应用（教材P270例4） 年份 1 2 3 4 5
购置费 维修费
11 5
11 6
12 8
12 11
13 18
最优更新方案：1.第一年和第三年购置新设备；2.第一年和第四 年购置新设备。总费用为53。 59
Ch6 Graph and Network
2012年12月31日星期一 Page 12 of 14
**任意两点间最短距离的矩阵算法**（选讲） 【例】在下图中用矩阵计算法求各点之间的最短距离 【解】定义dij为图中两相邻点的距离，若i与j不相邻，令dij=∞。则 ② 5 ① 2 ③ 7 4 2 ④ 2 ⑥ 7 6 1 6 ⑤ 3 ⑦
v1 v2 v3 v4 0 －1 －2 3 6 0 －3 0 －5 0
－1 －1
v5
2
k=3 k=4 0 0 －5 －5
－2 －2
1
2 0 1 －3 0 1 0 －5
－7 －7 －7 1 －3 －3 －1 －1 －1 5 －5 －5 6 6
§6.3 最短路问题
Shortest Path Problem
当vi到vj之间没有弧连接时，令wij＝＋∞
列表迭代计算： 设vs到vj经过vi到达vj，则vs到vj的最短距离为： －2
①
3
② －2 ③
d (vs，v j ) min d (vs，vi ) wij
i
迭代：
d (1) (vs，v j ) wsj
i
d ( k ) (vs，v j ) min d ( k 1) (vs，vi ) wij
则对vp点 r是所有已标号的点， Lsp min Lsr Lrp , 标号 r, p p是所有与已标号的典相邻的点
并将Lsp的值标注在该点旁，表示该点已标号； 4.重复第3步，一直到点vr得到标号为止。
§6.3 最短路问题
Shortest Path Problem
d13 d 23 d 33 d 43 d 53 d 63 d 73
d14 d 24 d 34 d 44 d 54 d 64 d 74
d15 d 25 d 35 d 45 d 55 d 65 d 75
d16 d 26 d 36 d 46 d 56 d 66 d 76
d17 d 27 d 37 d 47 d 57 d 67 d 77
Ch6 Graph and Network
2012年12月31日星期一 Page 5 of 14
【例】求下图v1到v7的最短路长及最短路线 3 5 5 v2 2
7
6
6 7 v5 3 7 1 2 6 v6 4 6 v7 10
1 0 v1
2 2 v3 2 4 7
5 v4 7
顶点编号 顶点标号 标号顺序 边长
1-3-2 1-3-2
v3
v4 v5 v6 v7
－3
－1
0
－5
0 0 1 －1
1
2
1-4
1-3
1-2-5
1-3
1-32-5 1-34-7
－2
－7 －3 －1 －5
1-3-4 1-3-4
0
1 0
7
1-3-6 1-3-6 1-4-7
v8
－3
－5
0
1-36-8
6
§6.3 最短路问题
Shortest Path Problem
v7已标号，计算结束。从v1到v7的最短路长是 10 最短路线是：v1 v3 v6 v5 v7
§6.3 最短路问题
Shortest Path Problem
Ch6 Graph and Network
2012年12月31日星期一 Page 6 of 14
从上例知，只要某点已标号，说明已找到起点vs到该点的最短路 线及最短距离，因此可以将每个点标号，求出vs到任意点的最短 路线，如果某个点vj不能标号，说明vs不可达vj .
求最短路有两种算法，一是求从某一点至其它各点之间最短离的狄 克斯屈拉(Dijkstra)算法；另一种是求网图上任意两点之间最短的矩 阵算法。
§6.3 最短路问题
Shortest Path Problem
Ch6 Graph and Network
2012年12月31日星期一 Page 2 of 14
§6.3 最短路问题
Shortest Path Problem
Ch6 Graph and Network
2012年12月31日星期一 Page 1 of 14
最短路问题 最短路问题，就是从给定的网络图中找出一点到各点或任意两点之 间距离最短的一条路 . 有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整 数规划和动态规划的问题，也可以归结为求最短路的问题。因此这 类问题在生产实际中得到广泛应用。
Shortest Path Problem
Ch6 Graph and Network
2012年12月31日星期一 Page 10 of 14
wij
v1 v2
d ( k ) (v1 , v j )
v6 v7 v8 k=1 k=2 0 0 －1 －5 －2 －2
3 7 0
v3 v4 v5 v6 v7 v8
6
所有点都已标号，点上的标号就是v1到该点的最短距离，最短路 线就是红色的链。
§6.3 最短路问题
Shortest Path Problem
Ch6 Graph and Network
2012年12月31日星期一 Page 8 of 14
有负权的最短路算法 假设图中没有负回路。如下图是一条负回路，最短路权无下界。
§6.3 最短路问题
Shortest Path Problem
Ch6 Graph and Network
2012年12月31日星期一 Page 13 of 14
d11 d 21 d 31 d 41 d 51 d 61 d 71
d12 d 22 d 32 d 42 d 52 d 62 d 72
v 2 v3 也一定是 v4
的最短路。见下图： v2 v4
v5 v4 v2 v1
v3
§6.3 最短路问题
Shortest Path Problem
Ch6 Graph and Network
2012年12月31日星期一 Page 4 of 14
设网络图的起点是vs,终点是vt ,以vi为起点vj为终点的边记为（i，j）, 距离为dij，若i与j不相邻，则dij=∞。显然dii=0,若用Lsi表示从vs到vi的 最短距离，现要求从vs到vt的最短距离，用Dijkstra算法时步骤如下： 1.从点vs出发，因Lss=0,将此值标注在该点旁的小方框内，表示该点 已标号； 2.从点vs出发，找出与该点相邻的点种距离最小的一个，设为vr ,将 Lsr=Lss+dsr的值标注在vr旁的小方框内，表明该点也已标号； 3.从已标号的点出发，找出与这些点相邻的所有未标号的点vp.若有
南岸
§6.3 最短路问题
Shortest Path Problem
Ch6 Graph and Network
2012年12月31日星期一 Page 3 of 14
狄克斯屈拉(Dijkstra)标号算法 这种算法的基本的基本思路是：假定 v1 v2 v3 v4 是 v1 v4 的最短路，则 v1 v2 v3 一定是 v1 v3 的最短路，
渡河问题
一老汉带了一只狼、一只羊、一棵白菜想要从南岸过河到北岸， 河上只有一条独木舟，每次除了人以外，只能带一样东西；另外， 如果人不在，狼就要吃羊，羊就要吃白菜，问应该怎样安排渡河， 才能做到既把所有东西都运过河去，并且在河上来回次数最少？这 个问题就可以用求最短路方法解决。 设：M—人 渡河方案共有10种，构造如下一个图，每条边的距离 W—狼 为1，问题变为求一条从MWSV到φ的最短路。 S—羊 北岸 V—白菜
0 5 2
5
0 2 7 0 7 4 2 7 0 6 2 7 6 0 1 3 4 2 1 0 6 3 6 0 2
步骤:1.
§6.3 最短路问题
Shortest Path Problem
§6.3 最短路问题
Shortest Path Problem
Ch6 Graph and Network
2012年12月31日星期一 Page 7 of 14
【例】求下图v1到各点的最短路及最短距离 4
② 4 0 ① 2 5 6 3 ③ 1 ④ 2
7
3 9 3
6
⑤ 2 12 16
⑥
6
⑧ 18
8
⑦18 Nhomakorabea当d ( k ) (vs，v j ) d ( k 1) (vs，vi )时得到最短路
§6.3 最短路问题
Shortest Path Problem
Ch6 Graph and Network
2012年12月31日星期一 Page 9 of 14
【例】求下图v1到v8的最短路长及最短路线
§6.3 最短路问题
wij v1 v1 v2 0 6 v2 －1 0 v3 －2 v4 3 2 v5 v6 v7 v8 k=1 1-1 1-2
Ch6 Graph and Network
2012年12月31日星期一 Page 11 of 14
d ( k ) (v1 , v j )
k=2 1-1 路线 距离 1-1 0 －5
22
① 16 ② 16
30
③ 17 ④