function?[f?wf?zwf]=BGf（Cb）

%?function?[f?wf?zwf]=BGf（Cb）
%?計算給定圖的最小費用最大流
%?C;%弧容量
%?b;%弧上單位流量的費用
%?f?最小費用最大流矩陣，wf?最大流量?zwf?最小費用

n=size（C2）;
wf=0;wf0=Inf;?%wf表示最大流量?wf0表示預定的流量值
f=zeros（nn）;?%取初始可行流f?為零流
while（1）
??????a=ones（nn）*inf;
??????for（i=1:n）
???????????a（ii）=0;
??????end%構造有向賦權圖
??????for（i=1:n）
??????????for（j=1:n）
??????????????if（C（ij）>0&f（ij）==0）
??????????????????a（ij）=b（ij）;
??????????????elseif（C（ij）>0&f（ij）==C（ij））
??????????????????a（ji）=-b（ij）;
??????????????elseif（C（ij）>0）a（ij）=b（ij）;
??????????????????a（ji）=-b（ij）;
??????????????end
??????????end
??????end
??????for（i=2:n）
??????????p（i）=Inf;s（i）=i;
??????end?%用Ford?算法求最短路?賦初值
??????for（k=1:n）
??????????pd=1;?%求有向賦權圖中vs?到vt?的最短路
??????????for（i=2:n）
??????????????for（j=1:n）
??????????????????if（p（i）>p（j）+a（ji））
??????????????????????p（i）=p（j）+a（ji）;s（i）=j;pd=0;
??????????????????end
??????????????end
??????????end
??????????if（pd）
??????????????break;
??????????end
??????end?%求最短路的Ford?算法結束
??????if（p（n）==Inf）
??????????break;
??????end?%不存在vs?到vt?的最短路?算法終止。?注意在求最小費用最大流時構造有向賦權圖中不會含負權回路?所以不會出現k=n
????dvt=Inf;t=n;?%進入調整過程?dvt?表示調整量
while（1）?%計算調整量
??????if（a（s（t）t）>0）
??????????dvtt=C（s（t）t）-f（s（t）t）;?%前向弧調整量
??????elseif（a（s（t）t）<0）
??????????dvtt=f（ts（t））;
??????end?%后向弧調整量
??????if（dvt>dvtt）
??????????dvt=dvtt;
??????end
??????if（s（t）==1）
??????????break;
??????end?%當t?的標號為vs?時?終止計算調整量
??????t=s（t）;
end?%繼續調整前一段弧上的流f
pd=0;
if（wf+dvt>=wf0）
????dvt=wf0-wf;pd=1;
end%如果最大流量大于或等于預定的流量值
t=n;
while（1）?%調整過程
????if（a（s（t）t）>0）
????????f（s（t）t）=f（s（t）t）+dvt;?%前向弧調整
????elseif（a（s（t）t）<0）
????????f（ts（t））=f（ts（t））-dvt;
????end?%后向弧調整
????if（s（t）==1）
????????break;
????end?%當t?的標號為vs?時?終止調整過程
????t=s（t）;end
????if（pd）
????????break;
????end%如果最大流量達到預定的流量值
????wf=0;?
????for（j=1:n）
????????wf=wf+f（1j）;
????end
end?%計算最大流量
zwf=0;
for（i=1:n）
????for（j=1:n）
????????zwf=zwf+b（ij）*f（ij）;
????end
end%計算最小費用
f;?%最小費用最大流

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2015-09-01?20:05??圖論算法及其MATLAB實現（全書+源代碼）\
?????文件????25530730??2012-05-05?15:08??圖論算法及其MATLAB實現（全書+源代碼）\圖論算法及其MATLAB實現.pdf
?????目錄???????????0??2015-09-01?20:39??圖論算法及其MATLAB實現（全書+源代碼）\源代碼\
?????文件????????2320??2009-08-28?16:21??圖論算法及其MATLAB實現（全書+源代碼）\源代碼\BGf.m
?????文件?????????514??2009-09-12?21:30??圖論算法及其MATLAB實現（全書+源代碼）\源代碼\boundnetf.m
?????文件?????????704??2010-01-25?23:07??圖論算法及其MATLAB實現（全書+源代碼）\源代碼\centgraf.m
?????文件?????????738??2009-08-28?16:32??圖論算法及其MATLAB實現（全書+源代碼）\源代碼\cn2shorf.m
?????文件?????????661??2009-09-12?20:26??圖論算法及其MATLAB實現（全書+源代碼）\源代碼\colorcodf.m
?????文件?????????995??2009-08-28?16:34??圖論算法及其MATLAB實現（全書+源代碼）\源代碼\concom.m
?????文件????????1924??2009-09-12?20:19??圖論算法及其MATLAB實現（全書+源代碼）\源代碼\graphcodf.m
?????文件?????????872??2010-05-07?23:01??圖論算法及其MATLAB實現（全書+源代碼）\源代碼\incandadf.m
?????文件????????1039??2009-08-28?21:40??圖論算法及其MATLAB實現（全書+源代碼）\源代碼\Krusf.m
?????文件?????????858??2010-05-07?23:01??圖論算法及其MATLAB實現（全書+源代碼）\源代碼\mattransf.m
?????文件????????1554??2009-08-28?21:20??圖論算法及其MATLAB實現（全書+源代碼）\源代碼\Primf.m
?????文件?????????367??2015-09-01?20:38??圖論算法及其MATLAB實現（全書+源代碼）\源代碼\shortdf.m