L2(vj) 0*v?A431*???????? v*?v4，d(v1,v4)?L2(v*)?minL2(vj)?1，前列顶点v1；
vjk?3 v10*v?Av24v33*v41*v57v6v7v8 L3(vj)?????? v*?v3，d(v1,v3)?L3(v*)?minL3(vj)?3，前列顶点v1；
vjk?4 v10*v24*v?Av33*v41*v57v6v7v8 L4(vj)?????? v*?v2，d(v1,v2)?L4(v*)?minL4(vj)?4，前列顶点v1；
vj k?5 v10*v24*v?Av33*v41*v5v6v7v8 L5(vj) 7*?????? v*?v5，d(v1,v5)?L5(v*)?minL5(vj)?7，前列顶点v4；
vjk?6 v10*v24*v?Av33*v41*v5v6v7v8 L6(vj)7*??10*?? v*?v7，d(v1,v7)?L6(v*)?minL6(vj)?10，前列顶点v5；
vjk?7 v10*v24*v33*v41*v5v6v7v8 L7(vj)7*??*10*?? 已经无法继续，因此从v1无法到达v6和v8。v1到其他各顶点的最短路径和长分别为：
v1?v2,d(v1,v2)?4
v1?v3,d(v1,v3)?3
v1?v4,d(v1,v4)?1
v1?v4?v5,d(v1,v5)?7 v1?v4?v5?v7,d(v1,v7)?10
9.17 解：(1)首先确定所有的割集与对应的容量。
①若V1?{vS}，则其割集为(V1,V1)?{(vS,v1),(vS,v2)}，则该割集相应的容量
45
为c(V1,V1)?cS1?cS2?4?2?6；
②若V2?{vS,v1}，则其割集为(V2,V2)?{(vS,v2),(v1,vT)}，，则该割集相应的容量为c(V2,V2)?cS2?c1T?4?3?7；
③若V3?{vS,v1,v2}，则其割集为(V3,V3)?{(v2,v3),(v1,vT)}，则该割集相应的容量为c(V3,V3)?c23?c1T?2?3?5；
④若V4?{vS,v1,v2,v3}，则其割集为(V4,V4)?{(v1,vT),(v3,vT)}，则该割集相应的容量为c(V4,V4)?c1T?c3T?3?5?8；
⑤若V5?{vS,v2}，则其割集为(V5,V5)?{(vS,v1),(v2,v1),(v2,v3)}，则该割集相应的容量为c(V5,V5)?cS1?c21?c23?2?3?2?7；
⑥若V6?{vS,v2,v3}，则其割集为(V6,V6)?{(vS,v1),(v2,v1),(v3,v1),(v3,vT)}，则该割集相应的容量为c(V6,V6)?cS1?c21?c31?c3T?2?3?1?5?11；
(2)上述各割集中，最小割集的容量为c(V*,V*)?minc(Vi,Vi)?c(V3,V3)?5，
i此时最小割集为V*?{vS,v1,v2},V*?{v3,vT}。
(3)根据最大流量最小割集定理，在该网络中，其最大流f*的流量为
V(f*)?min{c(Vi,Vi)}?c(V*,V*)?5。
i由于f23?f1T?2?3?5，所以图中标出的流就是最大流。
9.18 解：已知网络最大流为W(f)?11。只要求流量为11时的最小费用流即可。
（1）从f(0)?{0}开始，作长度网络L(f(0))，见图9-47(a)，用Dijkstra算法求出L(f(0))的最短路为：vS?v2?v1?vT。在网络中相应的可增广链上用最大流算法进行流的调整：
Q??{(vS,v2),(v2,v1),(v1,vT)}，Q???
8?0,5?0,7?0}?5 ?1?min{min(cij?fij(0)),minfij(0)}?min{Q?Q? 46
f(1)(0)??fij??1??(0)??fij(vi,vj)?Q?，
其他W(f(1))?W(f(0))??1?5 d(f(1))?5?1?5?2?5?1?20
f(1)的结果见图9-47 (b)。
（2）作长度网络L(f(1))如图9-47 (c)，弧上有负权，故只能采取逐次逼近法求最短路，最短路为vS?v1?vT。在网络中相应的可增广链上用最大流算法进行流的调整：
Q??{(vS,v1),(v1,vT)}，Q???
10?0,7?5}?2 ?2?min{min(cij?fij(1)),minfij(1)}?min{Q?Q?f(2)(1)??fij??2??(1)f??ij(vi,vj)?Q?，
其他W(f(2))?W(f(1))??2?7
d(f(2))?5?1?5?2?7?1?2?4?30
f(2)的结果见图9-47(d)。
（3）作长度网络L(f(2))如图9-47(e)，弧上有负权，故只能采取逐次逼近法求最短路，最短路为vS?v2?v3?vT。在网络中相应的可增广链上用最大流算法进行流的调整：
Q??{(vS,v2),(v2,v3),(v3,vT)}，Q???
?3?min{min(cij?fij(2)),minfij(2)}?min{8?5,10?0,4?0}?3
Q?Q?f(3)(2)??fij??3??(2)f?ij?(vi,vj)?Q?，
其他W(f(3))?W(f(2))??3?10
d(f(3))?8?1?5?2?7?1?2?4?3?3?3?2?48 f(3)的结果见图9-47(f)。
47
（4）作长度网络L(f(3))如图9-47(g)，弧上有负权，故只能采取逐次逼近法求最短路，最短路为vS?v1?v2?v3?vT。在网络中相应的可增广链上用最大流算法进行流的调整：
Q??{(vS,v1),(v2,v3),(v3,vT)}，Q??{(v1,v2)}
10?2,10?3,4?3,5}?1 ?4?min{min(cij?fij(3)),minfij(3)}?min{Q?Q?f(4)?fij(3)??4(vi,vj)?Q??(3)???fij??4(vi,vj)?Q，W(f(4))?W(f(3))??4?11 ?(3)其他?fijd(f(4))?8?1?4?2?7?1?3?4?4?3?4?2?55 f(4)的结果见图9-47(h)。
由于W(f(4))?11，f(4)就是所求的最小费用流，最小费用为55。
v141vT0vv110555vT0vS1622vSv2(a)
3v3v3v20 L(f(0)) (b) f(1)
–1v1461v1vT227vT0vS1–2vS505–13v3v3v20v2(c)L(f(1) ) (d) f(2)
48