第1步 由零流开始，即对所有的弧(x, y), f(x, y)=0。 第2步 因为对所有的弧(x, y), f(x, y) 第3步 用流的增值算法找一条从s至t的流的增值链。显然，可以看出从s至t有几条增值链。假设找到一条流的增值链为(s, a), (a, b), (b, t)。沿着这条链的最大流的增值是 min {i (s, a), i (a, b), i (b, t)}= min {2, 3, 2 }=2 这表明，在这条链中，三条弧(s, a), (a, b), (b, t)中的每一条最多可以增加两个单位流量：f (s, a)=2, f (a, b)=2. f (s, b)=0, f (b, t)=2, f (a, c)=0, f (c, t)=0。返回第2步。 第2步 对上面新产生的流，把弧重新分类。 f (s, a)= 2 = c (s, a) (s, a)?I (s, a)∈R, r(s, a)=2 f (a, b)= 2 < c (a, b) (a, b)∈I, i(a, b)=3-2=1 (a, b)∈R, r(a, b)=2 f (b, t)= 2 = c (b, t) (b, t) ?I (b, t)∈R, r(b, t)=2 f (s, b)= 0 < c (s, b) (s, b)∈I, i(s, b)=3 (s, b) ?R f (a, c)= 0 < c (a, c) (a, c)∈I, i(a, c)=4 (a, c) ?R f (c, t)= 0 < c (c, t) (c, t)∈I, i(c, t)=1 (c, t) ?R 第3步 用算法7-7寻找另一条流的增值链。执行算法7-7后得到唯一的流的增值链为(s, b),(a, b),(a, c), (c, t)。沿着这条链的最大可能流的增值是 min {i(s, b), r(a, b), i(a, c), i(c, t)}=min{3,2,4,1}=1 因此，沿着这条链有一个追加的单位流量从s运送至t。这条链的每一条前向弧(s, b),(a, c),(c, t)的流增加一个单位，这条链的后向弧(a, b)的流减少一个单位。最终得到流： f(s, a)=2, f(a, b)=1, f(b, t)=2, f(s, b)=1. f(a, c)=1, f(c, t)=1 到此，单位流量通过下列路线： 1个单位流量从s经(s, a),(a, b),(b, t)至t。 1个单位流量从s经(s, b),(b, t)至t。 1个单位流量从s经(s, a),(a, c),(c, t)至t。 返回第2步。 第2步 对上面新产生的流，把弧重新分类。 f (s, a)= 2 = c (s, a) (s, a) ?I (s, a)∈R, r(s, a)=2 f (a, b)= 1 < c (a, b) (a, b)∈I, i(a, b)=2 (a, b)∈R, r(a, b)=1 f (b, t)= 2 = c (b, t) (b, t) ?I (b, t)∈R, r(b, t)=2 f (s, b)= 1 < c (s, b) (s, b)∈I, i(s, b)=2 (s, b)∈R, r(s, b)=1 f (a, c)= 1 < c (a, c) (a, c)∈I, i(a, c)=3 (a, c)∈R, r(a, c)=1 f (c, t)= 1 = c (c, t) (c, t) ?I (c, t)∈R, r(c, t)=1 再次执行算法7-7，可以对顶点s,b,a,c(按此顺序)着色，但不能对t着色。所以找不到新的流的增值链，算法7-8终止。终止流（如上所述）就是最大流，因此，从s至t最多可以运送3个单位流量。 第三讲：最小费用流问题 计算机 最大流问题，是在一个有容量的图中，怎样从发点至收点运送最大可能的单位数量。 现在考虑这样一个问题：在一个有容量的图中，使用其中每条弧运送一个单位流量都需要一定的费用，这样送 s到t以最小费用运送一个给顶数V的单位流量。这个问题称为最小费用流的问题。 以a(x,y)表示沿着弧a(x,y)运送一个单位流量的费用。想设a(x,y)为正整数，然 后再讨论a(x,y)为非整数时的情况。 F(x,y)仍表示通过(x,y)的流的单位数量。F（X，Y）≥0。V表示从S运送至T的 单位数量。 最小费用流问题可以表示如下： MIN{∑(X,Y)A(X,Y)F(X,Y)} (7-13) 约束条件为 ∑Y [F(S,Y)-F(Y,S)] = V (7-14) ∑Y[F(X,Y)-F(Y,X)]= 0 (7-15) ∑Y[F(T,Y)-F(Y,T)]= -V (7-16) 0≤F(X,Y)≤C(X,Y) （对所有的弧（X，Y） （7-17） 其中式（7-13）表示流的总费用。式（7-14）表明从S发出的净流一定等于V。式（7-15）说明从任一顶点（非S和T）发出的净流一定等于0。式（7-16）说明从T发出的流一定等于 –V。式（7-17）表示每条弧的流取值必须在0与C（X，Y）之间。 这个问题也是先行规划问题。它乐意看策划功能最大流问题的推广：弧的费用由零变成非零；最大流的数值V由常量变成变量。可以用下式代替 MAX{PV-∑（X，Y）A（X，Y）F（X，Y）} （7-18） 其中P是一适当大的数，如稍大于从S至T运送一个单位流量的最大费用的数。如果用P代表从S到T运送一个单位流量所得的利润，则式（7-18）表示在扣除运费之后的最大净利润，因此使式（7-18）最大的任一个留同时使式（7-13）最小。 下面介绍求解这个问题的一个算法，它称为最小费用流算法。它的是思路是：从S至T运送尽可能多的全程每单位总费用为0的单位。其次，S至T运送尽可能多的全程每单位总增加费用为1的单位。…。当总数为V的单位要紧从S运送至T时，或没有更多的单位可以从S运送至T时，无论哪种情况发生，算法终止。这就是说，算法先对P=0解式（7-14）~式（7-18） 其次对P=1解式（7-14）~式（7-18），再次，对P=2，…。 设算法已从S至T运送尽可能多的总增加费用为P-1的单位流量，为了确定从S至T运送每单位总增加费用为P的单位流量，算法要找出一条从S至T的增值链，此链有如下属性：沿着这条链运送一个单位流量，总的增加费用P。 为了说明这个想法，考虑图（）， 弧的费用已经在图上标出。从S运送一个单位流量至T的费用最小的路线是：（S，A），（A，B），（B，T）。单位流量的总费用为2+1+2=5。如果V=1，则此就构成了一个最小费用流。 若V=2。对图检查可以知道，剩下仅有的增值链为（S，B），（A，B），（A，T），这条链可以承担从S至T 的一个追加的单位流量。如果第二个单位流量从S出发，则第一个大呢流量在顶点B处代替第一个单位流量，路径为（S，B），（B，T）。这两个单位流量的总费用为 A（S，A）+A（A，T）+A（S，B）+A（B，T）=2+4+4+2=12 比原费用增加了7。所增加的7是从流的增值链（S，B），（A，B），（A，T）中按下列方式形成的： 在前进方向，使用弧（S，B）形成+4的费用， 在后退方向，使用（A，B），形成-1的费用 在前进方向，使用（A，T），形成+4的费用 总增加的费用+7 因此，算法必须找出一条流的增值链，这条链C具有性质：链C的前向弧的费用之和减区链的后向弧的费用之和等于P，既 ∑I∈CA（XI，YI）- ∑J∈C A（XJ-YJ） = P 要完成这一计算，就要对图中每个顶点X指定一个整数P（X）。这些顶点数值P（X）具有以下性质：P（S）=0，P（T）=P，0〈P（X）《=P，X〈〉S，T。算法仅沿着弧（X，Y）改变流量，弧（X，Y）有 P（Y）—P（X）=A（X，Y） （7-19） 如果算法找到一条从S至T由满足式（）的弧组成的流的增值链，则从S严重着条链送至T的每个单位的总增加费用等于P 算法：最小费用流算法 第一步 开始时，令每条弧（X，Y）中的流F（X，Y）等于0。对所有个顶点X，令 P（X）=0 第二步：决定哪些弧可以改变流量。令I为所有弧（X，Y）的集合。I中的弧（X，Y）有
相关推荐：
loading