計算最小費用最大流MATLAB源代碼

1、精選優(yōu)質(zhì)文檔-傾情為你奉上計算最小費用最大流MATLAB源代碼,文件名為mp_mc.mfunctionMm,mc,Mmr=mp_mc(a,c)A=a; %各路徑最大承載流量矩陣C=c; %各路徑花費矩陣Mm=0; %初始可行流設(shè)為零mc=0; %最小花費變量mcr=0;mrd=0;n=0;while mrd=inf %一直疊代到以花費為權(quán)值找不到最短路徑     for i=1:(size(mcr',1)-1)           if a(mcr(i),mcr(i+1)=inf  &#

2、160;              ta=A(mcr(i+1),mcr(i)-a(mcr(i+1),mcr(i);           else                 ta=a(mcr(i),mcr(i+1);           end          &

3、#160;n=min(ta,n); %將最短路徑上的最小允許流量提取出來     end     for i=1:(size(mcr',1)-1)           if a(mcr(i),mcr(i+1)=inf                 a(mcr(i+1),mcr(i)=a(mcr(i+1),mcr(i)+n;       

4、   else                 a(mcr(i),mcr(i+1)=a(mcr(i),mcr(i+1)-n;           end     end     Mm=Mm+n; %將每次疊代后增加的流量累加，疊代完成時就得到最大流量     for i=1:size(a,1)      &#

5、160;    for j=1:size(a',1)                 if i=j&a(i,j)=inf                       if a(i,j)=A(i,j) %零流弧                   

6、60;        c(j,i)=inf;                             c(i,j)=C(i,j);                       elseif a(i,j)=0 %飽合弧          &#

7、160;                  c(i,j)=inf;                             c(j,i)=C(j,i);                       elseif a(i,j)=0 %非飽合弧

8、                             c(j,i)=C(j,i);                             c(i,j)=C(i,j);                  &

9、#160;    end                 end           end     end     mcr,mrd=floyd_mr(c) %進行疊代，得到以花費為權(quán)值的最短路徑矩陣(mcr)和數(shù)值(mrd)     n=inf;end%下面是計算最小花費的數(shù)值for i=1:size(A,1)   

10、  for j=1:size(A',1)           if A(i,j)=inf                 A(i,j)=0;           end           if a(i,j)=inf             

11、    a(i,j)=0;           end     endendMmr=A-a; %將剩余空閑的流量減掉就得到了路徑上的實際流量，行列交點處的非零數(shù)值就是兩點間路徑的實際流量for i=1:size(Mmr,1)     for j=1:size(Mmr',1)           if Mmr(i,j)=0         

12、       mc=mc+Mmr(i,j)*C(i,j); %最小花費為累加各條路徑實際流量與其單位流量花費的乘積           end     endend利用福得算法計算最短路徑MATLAB源代碼,文件名為floyd_mr.mfunctionmr,mrd=floyd_mr(a)n=size(a,1);D,R=floyd(a); %通過福德算法得到距離矩陣(D)和路徑矩陣(R)mrd=D(1,n); %提取從起點1到終點n的最短距離rd=R(1,n); %提

13、取從起點1開始沿最短路徑上下一個點的編號(rd)mr=1,rd; %從起點1開始沿最短路徑到rd點的最短路徑while rd=n %通過循環(huán)將最短路徑依次提取出來，直到rd點就是最后一個點     mr=mr,R(rd,n);     rd=R(rd,n);end福得算法MATLAB源代碼,文件名為floyd.mfunctionD,R=floyd(a)n=size(a,1);D=a;for i=1:n  for j=1:n  R(i,j)=j;  endendR;for k=1:n  for i=1:n    for j=1:n      if D(i,