最短路问题
例6.7 求从1到8的最短路径
1
1 2 10 4 5 6 4 2 7
2
5
6 9 5 3 8 4
3
3
7
6
8
最短路问题
X={1}, w1=0
p1=0
1
1
2 p4=1 4 5 2 4 10
2
5
6 9 5 3 4 8
3
3
7
6
6
7
8
min {c12,c14,c16}=min {0+2,0+1,0+3}=min {2,1,3}=1
例6.7 如右图所示中按dijkstra算 法可得P(v1)=5为从vs→v1的最短 路长显然是错误的，从vs→v2→v1 路长只有3。
v2 8
-5
vs
5
v1
最短路问题
例6.8 设备更新问题。某公司使用一台设备，在每年年初， 公司就要决定是购买新的设备还是继续使用旧设备。如果购 置新设备，就要支付一定的购置费，当然新设备的维修费用 就低。如果继续使用旧设备，可以省去购置费，但维修费用 就高了。请设计一个五年之内的更新设备的计划，使得五年 内购置费用和维修费用总的支付费用最小。已知：
设备每年年初的价格表 年份 年初价格 1 11 2 11 3 12 4 12 5 13
最短路问题
设备维修费如下表
使用年数
每年维修费用
0-1
5
1-2
6
2-3
8
3-4
11
4-5
18
解：将问题转化为最短路问题，如下图：用vi表示“第i年年 初购进一台新设备”,弧（vi,vj）表示第i年年初购进的设备一 直使用到第j年年初。
最短路问题
X={1,2,4}
p1=0 p2=2 2 1 p4=1 4 5 6 p6=3 4 2 7 10
1
2
5
6 9 5 3 8 4
3
3
7
6
8
min {c16,c23,c25,c47}=min {0+3,2+6,2+5,1+2}=min {3,8,7,3}=3 X={1,2,4,6}, p6=3
最短路问题
最短路问题
从上例知，只要某点已标号，说明已找到起点vs到 该点的最短路线及最短距离，因此可以将每个点标 号，求出vs到任意点的最短路线，如果某个点vj不能 标号，说明vs不可达vj 。 注：无向图最短路的求法只将上述步骤2将弧改成边即可。
最短路问题
例6.6 求下图v1到各点的最短距离及最短路线。
4. 选一个点标号 b( l ) min k ( i , j ) | ( i , j ) B, 在终点vl处标 j 号b(l), 返回到第2步。 3. 计算集合B中弧k(i，j)=b(i)+dij的标号
最短路问题
例6.5 求下图v1到v7的最短路长及最短路线
T标号
②
P标号
7
5
⑤
5
8 0 ①
16 v3 17 V2 （16,1） (22,1) 30
8 6 6
5 10 5 ③ 2 ④ 2 3 5
37 4
9
10 14 7 11
⑦ 11
2 2
2 4
⑥ 4
最短路问题
v1到v7的最短路长及最短路线如图所示：
②
8 0 ① 2 6 2 ④ 2 5 ③ 3
5
⑤
5
3 4
10
⑦ 11
7 2 ⑥ 4
v7已标号，计算结束。从v1到v7的最短路长是 11, 最短路线： v1→ v4 → v6 → v7
最短路问题
定义： 1）人—M（Man），狼—W（Wolf）， 羊—G（Goat）， 草—H（Hay） 2） 点—— vi 表示河岸的状态 3） 边—— ek 表示由状态 vi 经一次渡河到状态 vj
4） 权——边 ek 上的权定为 1
我们可以得到下面的加权有向图
最短路问题
状态说明： v1,u1 =( M,W,G,H ); v2,u2 =(M,W,G); v3,u3 =(M,W,H); v4,u4=(M,G,H); v5,u5 =(M,G) 此游戏转化为在下面的二部图中求从 v1 到 u1 的最短路问题。
2
v1 v5
v3
最短路问题
求网络图的最短路，设图的起点是vs,终点是vt ,以vi为起点vj 为终点的弧记为 (i, j) 距离为dij P标号(点标号)：b(j) —起点vs到点vj的最短路长； T标号(边标号)： k(i,j)=b(i)+dij， 步骤： 1. 令起点的标号；b(s)＝0。
2. 找出所有vi已标号vj未标号的弧集合 B={(i, j)} 如果这样的 弧不存在或vt已标号则计算结束；
W13 =11+5+6=22
W34 =12+5=17
W36 =12+5+6+8=31
6 59 41 31 23 18
W24 =11+5+6=22 W25 =11+5+6+8=30 W26 =11+5+6+8+11=41
v1 16 v2 22 30 41 v4 23 41
59
W45 =12+5=17 W46 =12+5+6=23
X={1,2,3,4,5,6,7}, p3=8
最短路问题
X={1,2,3,4,6,7}
p1=0 p2=2 2 1 p4=1 4 5 6 p6=3 4 2 7 10 p3=8
1
2
5
6 p5=6 5 3 8 4 9
3
3
7
6
8
p7=3
p8=10
min {c38,c58,c78}=min {8+6,6+4,3+7}=min {14,10,11}=10
最短路问题
X={1,2,4,6,7}
p1=0 p2=2 2 1 p4=1 4 5 6 p6=3 4 2 7 10
1
2
5
6 p5=6 5 3 8 4 9
3
3
7
6
8
p7=3
min {c23,c25,c75,c78}=min {2+6,2+5,3+3,3+8}=min {8,7,6,11}=6 X={1,2,4,5,6,7}, p5=6
v1
v2
v3
v4
v5
v6
最短路问题 W =11+5=16
12
把所有弧的权数计算如下表，把权数赋到图中，再用 W35 =12+5+6=23 W14 =11+5+6+8=30 Dijkstra算法求最短路。
W15 =11+5+6+8+11=41
2 W16 =11+5+6++8+11+18=59 1 16 2 3 4 5 =11+5=16 W 23 6 1 3 22 16 4 30 22 17 5 41 30 23 17
X={1,2,3,4,5,6,7,8}, p8=10
最短路问题
X={1,2,3,4,6,7,8}
p1=0 p2=2 2 1 p4=1 4 5 6 p6=3 4 2 7 10 p3=8
1
2
5
6 p5=6 5 3 8 4 9
3
3
7
6
8
p7=3
p8=10
1到8的最短路径为{1，4，7，5，8}，长度为10。
4
②
4 4 6 9
7 11 3 6 9 12 3 3 6
6
⑤
2
12 18 8
16 24 12 18 24
0 ①
2
5 5
3 ③
8
⑥
⑧ 18
1
2
6
④ 2
8 10
⑦
6
最短路问题
v1到各点的最短距离及最短路线如图所示：
②
4 6 7 3 9 3 8
6
⑤
2
12
0 ①
2
5
③
⑥
6
16
⑧ 18
1
④ 2
18
⑦
所有点都已标号，点上的标号就是v1到该点的最短距离，最短 路线就是红色的链。
X={1,2,4,6}
p1=0 p2=2 2 1 p4=1 4 5 6 p6=3 4 2 7 10
1
2
5
6 9 5 3 8 4
3
3
7
6
8
p7=3
min {c23,c25,c47,c67}=min {2+6,2+5,1+2,3+4}=min {8,7,3,7}=3 X={1,2,4,6,7}, p7=3
运筹学
( Operations Research )
运 筹 帷 幄 之 中
第六章
图与网络分析
Graph Theory and Network Analysis
决 胜 千 里 之 外
最短路问题
如何用最短的线路将三部电话连起来？ 此问题可抽象为设△ABC为等边三角形，连接三顶点的路 线（称为网络）。这种网络有许多个，其中最短路线者显然 是二边之和（如AB∪AC）。
17 v5 31 23 18 v6
16 v3 17 22 30
W56 =13+5=18
最短路问题
最终得到下图，可知，v1到v6的距离是53，最短路径有两条： v1→v3→v6和 v1→v4→v6