求最小费用最大流算法MATLAB程序代码.doc

求最小费用最大流算法的MＡＴLAB 程序代码如下(算例）:
ｎ=5；
C=[0　15　１6 ０　0
０ 0 0　１３ 1４
0　１1 0 １7 0
０ 0 0 0 8
0　０　０ ０　０］； ％弧容量
b＝［０　4　1　０ ０
０　0 0 6 １
0 ２ 0 ３ 0
0　０　０ 0　2
0 0　0 0　０];　％弧上单位流量的费用
wｆ＝0；wｆ0=Inｆ; ％wｆ　表示最大流量,　wｆ0 表示预定的流量值
for（ｉ=１:n）fｏr（j=1：ｎ)f(i，ｊ）=0；ｅnd;eｎd %取初始可行流f 为零流
whiｌe（1）
for(ｉ＝1:n）ｆor（j=1：ｎ）ｉf(j～=i)a（i，j）=Inｆ；ｅｎd;eｎd；end％构造有向赋权图
ｆor(i＝1：n）for（ｊ=1:ｎ）if(C(i，j)〉0&f(i，j）==0）ａ（i,j)=ｂ（i,j）；
elｓeiｆ(C(i,j）〉0＆ｆ（i，j)==C(i,j)）a(ｊ，i）=—ｂ(i，j）；
eｌseiｆ(Ｃ（i,ｊ)〉０）ａ（i,ｊ）＝b(i，j)；a（j，ｉ）=—ｂ（i,j)；end；ｅｎd；end
for(i=２：ｎ）ｐ（i）＝Inf；ｓ（i)=i;enｄ ％用Ford 算法求最短路, 赋初值
fｏr（ｋ=１：n)pｄ=1； ％求有向赋权图中ｖｓ 到vｔ　的最短路
for(ｉ=2：n)ｆor（j=1：n）ｉf（p(i）〉ｐ（j)＋a（ｊ,i）)p(ｉ）＝p（ｊ）＋ａ（j，ｉ)；s(i)=j;pd=0；ｅnｄ；eｎd；end
iｆ（pd)ｂreaｋ；eｎd；end ％求最短路的Fｏrd　算法结束
if(p（n）==Ｉnf）bｒeａk;end　％不存在vs 到vt 的最短路, 算法终止。 注意在求最小费用最大流时构造有
向赋权图中不会含负权回路， 所以不会出现k=ｎ
dvｔ=Ｉnf；t＝n； %进入调整过程， dvt 表示调整量
wｈile（1）　％计算调整量
iｆ（a(s（t）,ｔ）〉0)ｄｖｔｔ=Ｃ(ｓ(t),t）－ｆ(s(ｔ),t）； ％前向弧调整量
eｌseif（ａ（s（ｔ),t）＜０)dvｔｔ＝ｆ(ｔ，s（t））；eｎd ％后向弧调整量
iｆ(dvt>dvtt）dvt=dｖｔｔ;end
if（s(t）=＝１)ｂreaｋ;end ％当ｔ 的标号为vｓ 时,　终止计算调整量
t=s(ｔ）;enｄ　％继续调