label2=setdiff(label2, record) list=union(list, labe 12)i pred(label2(find(pred(labe12)==0)))=-flagi maxf(label2 )=min(maxf(flag), f(label2, flag))i record=union(re cord, label2) end if maxf(n)>0 pred(v2)i if v1>0 f(vl, v2)=f(vl, v2)+maxf(n) vl=abs(v1) f(v2,v1)=f(v2, v1)-maxf(n)i end v2=v1 l=pred (v2) end end end §8最小费用流及其求法 最小费用流 上面我们介绍了一个网络上最短路以及最大流的算法,但是还没有考虑到网络上流 的费用问题,在许多实际问题中,费用的因素很重要。例如,在运输问题中,人们总是 希望在完成运输任务的同时,寻求一个使总的运输费用最小的运输方案。这就是下面要 介绍的最小费用流问题。 在运输网络N=(s,yV,A,U)中,设c是定义在A上的非负函数,它表示通过弧 ,j)单位流的费用。所谓最小费用流问题就是从发点到收点怎样以最小费用输送一已 知量为v(f)的总流量 最小费用流问题可以用如下的线性规划问题描述: min vO, i=s St ∑G-∑f={-v),i=t, j(,∈A(j,∈A 0.i≠S,t 0≤f≤4n,V(,)∈A 显然,如果v(∫)=最大流ν(~mx),则本问题就是最小费用最大流问题。如果 v()>(/m),则本问题无解 82求最小费用流的一种方法一迭代法 这里所介绍的求最小费用流的方法叫做迭代法。这个方法是由 Busacker和 Gowan 在1961年提出的。其主要步骤如下-66- label2=setdiff(label2,record); list=union(list,label2); pred(label2(find(pred(label2)==0)))=-flag; maxf(label2)=min(maxf(flag),f(label2,flag)); record=union(record,label2); end if maxf(n)>0 v2=n; v1=pred(v2); while v2~=1 if v1>0 f(v1,v2)=f(v1,v2)+maxf(n); else v1=abs(v1); f(v2,v1)=f(v2,v1)-maxf(n); end v2=v1; v1=pred(v2); end end end f §8 最小费用流及其求法 8.1 最小费用流 上面我们介绍了一个网络上最短路以及最大流的算法，但是还没有考虑到网络上流 的费用问题，在许多实际问题中，费用的因素很重要。例如，在运输问题中，人们总是 希望在完成运输任务的同时，寻求一个使总的运输费用最小的运输方案。这就是下面要 介绍的最小费用流问题。 在运输网络 N = (s,t,V, A,U) 中，设 ij c 是定义在 A 上的非负函数，它表示通过弧 (i, j) 单位流的费用。所谓最小费用流问题就是从发点到收点怎样以最小费用输送一已 知量为 v( f ) 的总流量。 最小费用流问题可以用如下的线性规划问题描述：  i j A ij ij c f ( , ) min s.t.           − = = − = j j i A ji j i j A ij i s t v f i t v f i s f f :( , ) :( , ) 0, , ( ), ( ), ， 0  f ij  uij , (i, j)  A. 显然，如果 v( f ) = 最大流 ( ) max v f ，则本问题就是最小费用最大流问题。如果 ( ) ( ) max v f  v f ，则本问题无解。 8.2 求最小费用流的一种方法—迭代法 这里所介绍的求最小费用流的方法叫做迭代法。这个方法是由 Busacker 和 Gowan 在 1961 年提出的。其主要步骤如下：