表示弧长 (图12) 解:k=0,由6.18中的数据作L(o)=[jo)和θ(o)=[0j(o)按(65)式计算 及按(66)式得表6-2(k=0,1,2)如下: 表62 0 02 0002 22-60 1234 1234 1222 1234 [On小k] 1234 1234 232 1234 1134 1131 由于L42=3<0,说明图12中含有顶点v的负回路Q,由[012]中的 042=1,0142)=2,0242)=4可知,负回路Q={v4,v,2,4},d4=L42)=-3,计算 终止。否则,继续计算下去,则会出现更多的负回路,且随着计算次数增 多,含有负回路P的长d→>-∞。因此,本题不存在从v到v的最短路 (lJ=1,2,3.4)。 §4.最大流问题 最大流问题是一类极为广泛的问题。不仅在交通运输网络中有人流 车流、货物流、供水网络中有水流、金融系统中有现金流、通讯网络中信33 表示弧长。 （图 12） 解：k=0，由 6.18 中的数据作 L(o)=[lij(o)]和(o)=[ij(o)],按(6.5)式计算 及按(6.6)式得表 6-2(k=0,1,2)如下： 表 6—2 k=0 k=1 k=2 [Lij(k)] 2 2 6 0 2 0 6 0 2 2 0 1 − −  −  −   2 1 6 0 2 0 6 0 2 2 0 1 − − −  −  −   2 1 6 3 2 0 4 0 2 2 0 1 3 1 − − − −  − −  − − [ij(k)] 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 1 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 1 3 1 1 2 3 2 1 2 3 4 1 2 2 2 由于 L44(2)=-3<0，说明图 12 中含有顶点 v4 的负回路 Q，由[ij(2) ]中的 44(2)=1, 14(2)=2, 24(2)=4 可知，负回路 Q={v4,v1,v2,v4}，d44=L44(2)=-3，计算 终止。否则，继续计算下去，则会出现更多的负回路，且随着计算次数增 多，含有负回路 P 的长 dij→-。因此，本题不存在从 vi 到 vj 的最短路 (i,j=1,2,3,4)。 §4. 最大流问题 最大流问题是一类极为广泛的问题。不仅在交通运输网络中有人流、 车流、货物流、供水网络中有水流、金融系统中有现金流、通讯网络中信