表 7-4 最小费用流计算表（之三)

运送追加的单位流量。因此，现有的三个单位的流就是具有最小费用的最大流。

到现在为止，以上我们的讨论都是假定边的费用 c（u，v)为正整数。以下我们来修正最小费用流的算法，以适应具有非整数边的费用。

因为边的费用均假设为正整数，所以从 s 至 t 所运送的所有单位流量担

负的总增加费用是正整数。因此，算法只须检验 P 的整数值，并且顶点数值总是增加整数+1。

当边的费用无需为整数时，则从 s 至 t 的流增值路的总费用不一定是整数，因而，算法必须检验不是整数的 P 值。算法应该检验 P 的哪些值呢？算法应该作出顶点数值的什么样的增量呢？

设算法对 P=P（t)的某些值已经执行过。某些边将有一个已着色端点和一个未着色端点。我们必须考虑以下两种情形：

第一种情形：如果顶点 u 已经着色，而顶点 v 未着色，则仅当（u，v)

∈I 且 P（v)可以改变，使 P（v)-P（u)=c（u，v)时，边（u，v)是可供选择为着色的边。如果（u，v)∈I，则 P（v)-P（u)≤c（u，v)。因而在边（u， v)可以着色之前，P（v)必须增加 c（u，v)-P（v)+P（u)个单位。令δ（u， v)=c（u，v)-P（v)+P（u)。

第二种情形：如果顶点 v 已着色，而顶点 u 未着色，则仅当（u，v)∈R 且 P（u)可以改变使 P（v)-P（u)=c（u，v)时，边（u，v)是可供选择为着色的边。如果（u，v)∈R，则 P（v)-P（u)≥c（u，v)。因而，在边（u，v)可以着色之前，P（u)必须增加 P（v)-P（u)-c（u，v)个单位。令δ（u，v)=P

（v)－P（u)－C（u，v)。

如果边（u，v)不适合于第一种情形或第二种情形，则令δ（u，v)

= ∞。令δ = min（u，v）｛δ（u，v）｝（u，v）＞0.

(u,v)

因此，如果每个未着色顶点 u 的对偶的数值 P（u)增加δ，则至少将有另外一条边可以着色，并且也许将发现一条新的流的增值链，所以，P（t) 的值将增加δ。同样地，为保证至少有另外一条边可以着色，需要最小的增量，确定这个增量，就可以算出以后各个顶点数值的增量。如果δ=∞，则没有另外的边可以着色，在这种情形时，现有的流就是最大流。于是，由修正顶点数值的增量过程，最小费用流算法就可以适用于非整数的边的费用。

修正的算法是否可以在有限个步骤以后结束呢？答案是肯定的。因为 P

（t)必然总是等于从 s 至 t 沿着某一条链的各条边的费用的总和，而且，因为从 s 至 t 仅存在有限条不同的链，从而在修正算法中，P（t)只能取有限个不同的数值。因此，修正的算法必然仅在有限个步骤以后结束。