最短路最大流练习题.doc

7　求图7.58中各图从到各点的最短路．
7

4
2
9
1
7
3
1
5
6
8

2

2
1
4
6
1

1
1
9

2
3

(a)

4

4
8
7
3
2
2
3
2
5
6

4

5
5
1
5
3

2
2
6

4
2

(b)

，k=5.
i=2
)，

令
对已经标号v3，（v3,v7）∈S,但v7已经标号。对已经标号v11，有（v10,v11）∈S,则T(v11)修改为P(v10)+w10-11=15+4=19,λ(v11)=10,所以P(v11)=19,
S9={ v1,v2,v5,v9,v4,v6,v8,v7,v3,v10,v11}
d(v1,v2)=2, 最短路为（v1,v2）;
d(v1,v5)=3, 最短路为（v1,v2,v5）;
d(v1,v9)=4, 最短路为（v1,v2,v5,v9）;
d(v1,v7)=14 ,最短路为（v1,v2,v5,v9,v6,v7）;
d(v1,v8)=11, 最短路为（v1,v2,v5,v9,v8）;
d(v1,v4)=8, 最短路为（v1,v2,v4）或（v1,v4）;
d(v1,v6)=10, 最短路为（v1,v2,v5,v9,v6）;
d(v1,v3)=15, 最短路为（v1,v2,v4,v3）或（v1,v4,v3）;
d(v1,v10)=15, 最短路为（v1,v2,v5,v9,v6,v7,v10）;
d(v1,v11)=19, 最短路为（v1,v2,v5,v9,v6,v7,v10,v11）;
结果标在图7.58(a’)上。
P(19,10)
P(14,6)
P(10,9)
P(4,5)
P(3,2)
P(8,1)
P(0,0)

4
2
9
1
7
3
1
5
6
8

2

2
1
4
6
1

1
1
7
9

2
3

P(2,1)
P(11,9)
P(15,4)
P(15,7)
图7.58(a’)

解 结果见图7.58(b’).
P(17,8)
P(11,7)
P(9,3)
P(8,4)
P(7,2)
P(6,1)
P(0,0)
4

4
8
7
3
2
2
3
2
5
6

4

5
5
1
5
3

2
2
6

4
2

图7.58(b’)
P(4,1)
P(3,1)
P(10,6)
P(14,7)

12 求图7.62中各图从到的最大流．

3

4

1

4
8
2
3
5
6
7

9

4
5
5
3
2
1

5
7

(a)

(3,2)
(3,2)
(10,4)

(2,2)
(1,1)
(4,3)
(3,2)

(4,3)

(4,2)
(5,3)
(8,3)
(7,6)
(b)
图7.62

(s,7)
(1,3)
(3,0)
(5,3)
(4,4)

(1,0)
(7,1)
(2,3)
(1,4)
(4,4)
(8,2)
(2,2)
(3,0)
(6,2)
(7,2)

(0,+∞)

(9,2)
(4,0)
(5,4)
(5,4)
(3,0)
(2,2)
(1,0)

(5,0)
(7,4)

(5,1)
(a’)

(3,3)
(3,3)
(10,7)
(s,3)

(2,2)
(1,1)
(4,4)
(3,3)

(0,+∞)

(4,4)

(4,4)
(5,5)
(8,7)
(7,7)
(b’)
图7.62

13 两家工厂和生产同一种商品，商品通过图7.63表示的网络送到市场．求从工厂到市场所能运送的最大总量．
18
7

6
2
8
13
19
3
24
24
2
4
7
12
7
15
7
4
5
22
图7.63

解 加上点，点同时给中间点加上名称，令所有弧的可行流都为0，如图7.63(1)所示，
(19,0)
(19,0)
(6,0)
(7,0)
(16,0)
(30,0)

(18,0)
(7,0)

(6,0)
(2,0)
(8,0)
(13,0)
(19,0)
(3,0)
(24,0)
(24,0)
(2,0)
(4,0)
(7,0)
(12,0)
(15,0)
(7,0)
(4,0)
(5,0)
(22,0)
图7.63(1)

（1）标号过程
用标号法找出增广链.(0,+),(,30),(,18),(,7),(,7),因已标号,故转入调整过程.
(19,0)
(19,0)
(6,0)
(7,0)
(16,0)
(30,0)

(18,0)
(7,0)

(6,0)
(2,0)
(8,0)
(13,0)
(19,0)
(3,0)
(24,0)
(24,0)
(2,0)
(4,0)
(7,0)
(12,0)
(15,0)
(7,0)
(4,0)
(5,0)
(22,0)
图7.63(2)

(2)调整过程
按点的第一标号找到一条增广链,如图7.63(2)中粗箭头表示.
按照=7,在上调整

由于本题图形复杂,调整过程次数过多,这里不再一步步进行计算,把进行几步计算后的结果直接写在图7.63(3)上.
(19,4)
(19,13)
(6,6)
(7,0)
(16,10)
(30,13)

(18,9)
(7,4)

(6,6)
(2,0)
(8,4)
(13,0)
(19,0)
(3,0)
(24,0)
(24,0)
(2,2)
(4,4)
(7,7)
(12,6)
(15,0)
(7,0)
(4,4)
(5,0)
(22,4)
图7.63(3)