由于b≥0，所以f={0}必是流量为0的最小费用流。这样， 总可以从子={0}开始算起。一般地，如果已知∫是流量为(f)的最 小费用流，余下的问题就是如何去寻找关于f的最小费用增广链。 为此，构造一个有向费用网络W(∫)，它的顶点与原网络完 全相同，而把原网络中的每一条弧(，)分解成方向相反的两条 弧，即(，y)和(V,)。并按如下规则定义W(f)中弧的权数： 当y，令仅数w,者 「b,若f∠c 当弧是原D中弧y的反向弧时，令权数w若》 上述定义式的含义是：在增广链的前向弧上，当f<©时，荪瑁 加流量，其单位费用为b,当=c,时不能再增加流量，香则要花 费高昂的代价，因此单位费用为+0。在增广链的后向弧上，当 0时，减少一个单位流量可节约的费用为b,当0时，由于无法 减少流量，因此单位费用亦为+0。 经上述处理后，在费用、容量网络中寻找关于f的最小费用增厅 链问题，就转化为在有向费用网络W(f)中寻找从？，→，以费用 表示的最短路。因是求最短路，故华=+∞的弧可以从网络中省略。 由于bij ≥0，所以 f =｛0｝必是流量为0的最小费用流。这样， 总可以从 f =｛0｝开始算起。一般地，如果已知 f 是流量为v(f )的最 小费用流，余下的问题就是如何去寻找关于 f 的最小费用增广链。 为此，构造一个有向费用网络W（ f ），它的顶点与原网络完 全相同，而把原网络中的每一条弧（vi ,vj）分解成方向相反的两条 弧，即（vi ,vj）和（vj , vi ）。并按如下规则定义W（ f ）中弧的权数： 上述定义式的含义是：在增广链的前向弧上，当 f ij ＜ cij 时，可以增 加流量，其单位费用为bij ，当 f ij =cij 时不能再增加流量，否则要花 费高昂的代价，因此单位费用为+∞。在增广链的后向弧上，当 f ij＞ 0时，减少一个单位流量可节约的费用为bij ，当 f ij=0时，由于无法 减少流量，因此单位费用亦为+∞。 经上述处理后，在费用、容量网络中寻找关于 f 的最小费用增广 链问题，就转化为在有向费用网络W（ f ）中寻找从vs →vt 以费用 表示的最短路。因是求最短路，故wij = +∞的弧可以从网络中省略。 ( )    + =   = ij ij ij ij ij f c b f c 若 若 当弧 D时，令权数 , , vi ,vj wij ( ) ( )    + = = , 0 - , 0 v ,v v ,v wji j i i j ij ij ij f b f 若 若 当弧 是原D中弧 的反向弧时，令权数 