Ⅴ Ⅴ 此表示：任务：Ⅳ →Ⅰ→Ⅱ 任务：Ⅴ→Ⅲ

共两只船就可完成5批货物的运输任务。当然，解不唯一。

第四讲：最小费用最大流

一．带负权的最短路问题：

大家知道，狄克斯特洛法求最短路只适应于权wij≥0的情况，当网络中出现负权时，此法失效，如：

求v1到v3的最短路。

用Dijkstra标号法：给v1标号v1（0），min ｛2,3｝=2, 所以v3（2）。终止。 答案：v1—v3，长度为2。事实上，v1—v2—v3长度为1。 ？ 此法失败。 下面通过例子来说明带负权的网络的最短路求法：逐次逼近法：

v5（6）（3） 4 v2（2）

2 -2 -3 3 v3（1）（0） 4 5 0） v1（6 v6（6）

-3 4 2 -1 v4（-3） 7 v7（4）

图8-54 1．给v1标号v1（0）。画圈。

2。求min｛k12, k13, (k14)｝=-3. 给v4标号v4（-3）。（v1，v4）画粗线。画第二个圈。

v23 -2 v1（0） 2 v3（2）

v8（10） 13

3。求min｛k12, k13, (k43), k47｝=1, 给v3标号v3（1）。画第三个圈。

4。求min｛(k12), k36, k47｝=｛2,4,7｝=2, 给v2标号v2（2）。画第四个圈。（注意：此时大圈时要留出出线（v2，v3））。

5．求 min｛k25, (k23), ,k47｝=min｛6,0,7,4｝=0, 此时，将v3的标号修改成v3（0），且以较小标号为准。（后标号较小，修改，大，不修改）。画第五个圈，此时，因（v2，v3）已考察，划入内。

6．求min｛(k25), (k36)｝=min｛6,6｝=6, 给v5,v6都标号v5（6），v6（6）。画第六个圈。

7．求min｛(k65), k68｝=min｛3,10｝=3, 给v5重新标号v5（3）。画第七个圈。 8．求min｛(k68)｝=10, 给v8标号v8（10）。画第八个圈。

9．求min｛k87, k76，k74)｝=min｛9,6, 11｝=6, 均大于现有的标号数，已没有改动的必要。完毕。

从v8倒序找最短路线：v1—v4—v7—v6—v8。距离：10。

§5 最小费用流的问题

前两节主要讲了两个问题：最短路问题和最大流问题。下面介绍网络中二者的结合问题：最小费用流的问题。

问题的提出是这样的：在一个关于流的网络中，人们不仅需要流达到一定的数量，（甚至达到最大，即最大流）而且每一个流量要有一定的费用，流所走的路线不一样，单位费用不一样。同样数量的流量，可能走的路线不一样，总的费用不一样。从而在限定网络流的基础上，让流沿那些边走，能使总的费用最小（这里的最小费用问题又看成最短路问题）。

特别的，当最大流不惟一时，在所有最大流中求一个流f,使总费用最低。

用规划语言可以这样描述：若给定容量网络G=（V，E，C），除给每边（（vi，vj）∈E）上的容量（cij∈C）外，还给流量的费用dij≥0，记为

G=（V，E，C，D）

若给定G的一个可行流f=｛fij｝，在总的流量W（f）=v（常数）下使 mind(f)=

W(f)?v(vi,vj)?E?dijfij

(0)求最费用最大流的基本思想是：从零流f=｛0｝=｛fij｝开始，以费用作为边的长

14

度，用最短路方法，求出可增广链，调整流量，使之流逐步达到要求的数量。

下通过例子来说明。

例：在图8-55所示的网络中，求流量v为10的最小费用流。边上括号内为（cij，dij）。 解： v1 （7，1） （10，4） vt v（2，6） s （5，2） （8，1） （4，2） v3（10，3） v2

图 （a）

先假设此网络是空架子，即0-流。 v1 （7，0，1） （10，0，4）

vt vs （2，0，6） （5，0，2） （8，0，1） （4，0，2） v3v （10，0，3） 2

然后，逐步调整流量到10，在什么路线上增加流量？在费用最小的路线上调流量。为简单，把费用网络先拿出来。借费用最短路作为可行流的可增广链，从而在保证流量的同时，又保证费用最低。看下图：

v1 1 4

vt vs 2 6

2 1 3 v3v2

图 （b）L(f(0))

在0流（b）上找最短路。

v1（3） 1 4

2 6 2 v s1 （0）

3 v3（4） v2（1）

vt（4）

15

在此可增广链上，取容量最小的值min｛8,5,7｝=5, 调整量为5。调整后图为

v1 （7，5） （10，0）

vt vs（5，5） （2，0） （4，0） （8，5） （10，0） v3v2

图 （c）f此时，网络流量为W(f(1)(1)

(1))=5?10，此流的费用为d(f)=5×1＋5×2＋5×1=20。

返回到费用网络中，继续找最短路，进而继续调整。在下面流量的调整中，注意到图（c)有些边的流量已饱和，只能降低，不能再升，如（v2，v1）。而有些边可降，可升。如 （v1，vt）。下次调整为了表达上面的意思，我们在费用流网络中，可升、可降的边用两个箭头表示，如下图：

4

vs 1 -1

v1 -2 -1 1 6 2 vt

v23 v3(1) 图 (d ) L(f)

下用逐次逼近法求vs到vt的费用最短路。

4 v s（0） 1 -1

v1（4） 1 -2 6 -1 vt2 3 （5） v3v2（1） (1)（4） 图（d）L(f1 标v（0）○，画第一个圈。 s)

16