-
大小:文件類(lèi)型: .zip金幣: 2下載: 2 次發(fā)布日期: 2023-06-22
- 語(yǔ)言: Matlab
- 標(biāo)簽:
資源簡(jiǎn)介
圖論算法及其MATLAB實(shí)現(xiàn)(全書(shū)+源代碼)
代碼片段和文件信息
function?[f?wf?zwf]=BGf(Cb)
%?function?[f?wf?zwf]=BGf(Cb)
%?計(jì)算給定圖的最小費(fèi)用最大流
%?C;%弧容量
%?b;%弧上單位流量的費(fèi)用
%?f?最小費(fèi)用最大流矩陣,wf?最大流量?zwf?最小費(fèi)用
n=size(C2);
wf=0;wf0=Inf;?%wf表示最大流量?wf0表示預(yù)定的流量值
f=zeros(nn);?%取初始可行流f?為零流
while(1)
??????a=ones(nn)*inf;
??????for(i=1:n)
???????????a(ii)=0;
??????end%構(gòu)造有向賦權(quán)圖
??????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;?%求有向賦權(quán)圖中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?算法結(jié)束
??????if(p(n)==Inf)
??????????break;
??????end?%不存在vs?到vt?的最短路?算法終止。?注意在求最小費(fèi)用最大流時(shí)構(gòu)造有向賦權(quán)圖中不會(huì)含負(fù)權(quán)回路?所以不會(huì)出現(xiàn)k=n
????dvt=Inf;t=n;?%進(jìn)入調(diào)整過(guò)程?dvt?表示調(diào)整量
while(1)?%計(jì)算調(diào)整量
??????if(a(s(t)t)>0)
??????????dvtt=C(s(t)t)-f(s(t)t);?%前向弧調(diào)整量
??????elseif(a(s(t)t)<0)
??????????dvtt=f(ts(t));
??????end?%后向弧調(diào)整量
??????if(dvt>dvtt)
??????????dvt=dvtt;
??????end
??????if(s(t)==1)
??????????break;
??????end?%當(dāng)t?的標(biāo)號(hào)為vs?時(shí)?終止計(jì)算調(diào)整量
??????t=s(t);
end?%繼續(xù)調(diào)整前一段弧上的流f
pd=0;
if(wf+dvt>=wf0)
????dvt=wf0-wf;pd=1;
end%如果最大流量大于或等于預(yù)定的流量值
t=n;
while(1)?%調(diào)整過(guò)程
????if(a(s(t)t)>0)
????????f(s(t)t)=f(s(t)t)+dvt;?%前向弧調(diào)整
????elseif(a(s(t)t)<0)
????????f(ts(t))=f(ts(t))-dvt;
????end?%后向弧調(diào)整
????if(s(t)==1)
????????break;
????end?%當(dāng)t?的標(biāo)號(hào)為vs?時(shí)?終止調(diào)整過(guò)程
????t=s(t);end
????if(pd)
????????break;
????end%如果最大流量達(dá)到預(yù)定的流量值
????wf=0;?
????for(j=1:n)
????????wf=wf+f(1j);
????end
end?%計(jì)算最大流量
zwf=0;
for(i=1:n)
????for(j=1:n)
????????zwf=zwf+b(ij)*f(ij);
????end
end%計(jì)算最小費(fèi)用
f;?%最小費(fèi)用最大流
?屬性????????????大小?????日期????時(shí)間???名稱(chēng)
-----------?---------??----------?-----??----
?????目錄???????????0??2015-09-01?20:05??圖論算法及其MATLAB實(shí)現(xiàn)(全書(shū)+源代碼)\
?????文件????25530730??2012-05-05?15:08??圖論算法及其MATLAB實(shí)現(xiàn)(全書(shū)+源代碼)\圖論算法及其MATLAB實(shí)現(xiàn).pdf
?????目錄???????????0??2015-09-01?20:39??圖論算法及其MATLAB實(shí)現(xiàn)(全書(shū)+源代碼)\源代碼\
?????文件????????2320??2009-08-28?16:21??圖論算法及其MATLAB實(shí)現(xiàn)(全書(shū)+源代碼)\源代碼\BGf.m
?????文件?????????514??2009-09-12?21:30??圖論算法及其MATLAB實(shí)現(xiàn)(全書(shū)+源代碼)\源代碼\boundnetf.m
?????文件?????????704??2010-01-25?23:07??圖論算法及其MATLAB實(shí)現(xiàn)(全書(shū)+源代碼)\源代碼\centgraf.m
?????文件?????????738??2009-08-28?16:32??圖論算法及其MATLAB實(shí)現(xiàn)(全書(shū)+源代碼)\源代碼\cn2shorf.m
?????文件?????????661??2009-09-12?20:26??圖論算法及其MATLAB實(shí)現(xiàn)(全書(shū)+源代碼)\源代碼\colorcodf.m
?????文件?????????995??2009-08-28?16:34??圖論算法及其MATLAB實(shí)現(xiàn)(全書(shū)+源代碼)\源代碼\concom.m
?????文件????????1924??2009-09-12?20:19??圖論算法及其MATLAB實(shí)現(xiàn)(全書(shū)+源代碼)\源代碼\graphcodf.m
?????文件?????????872??2010-05-07?23:01??圖論算法及其MATLAB實(shí)現(xiàn)(全書(shū)+源代碼)\源代碼\incandadf.m
?????文件????????1039??2009-08-28?21:40??圖論算法及其MATLAB實(shí)現(xiàn)(全書(shū)+源代碼)\源代碼\Krusf.m
?????文件?????????858??2010-05-07?23:01??圖論算法及其MATLAB實(shí)現(xiàn)(全書(shū)+源代碼)\源代碼\mattransf.m
?????文件????????1554??2009-08-28?21:20??圖論算法及其MATLAB實(shí)現(xiàn)(全書(shū)+源代碼)\源代碼\Primf.m
?????文件?????????367??2015-09-01?20:38??圖論算法及其MATLAB實(shí)現(xiàn)(全書(shū)+源代碼)\源代碼\shortdf.m
評(píng)論
共有 條評(píng)論