资源描述:
《计算最小费用最大流MATLAB源代码.doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、计算最小费用最大流MATLAB源代码,文件名为mp_mc.mfunction[Mm,mc,Mmr]=mp_mc(a,c)A=a;%各路径最大承载流量矩阵C=c;%各路径花费矩阵Mm=0;%初始可行流设为零mc=0;%最小花费变量mcr=0;mrd=0;n=0;whilemrd~=inf%一直叠代到以花费为权值找不到最短路径 fori=1:(size(mcr',1)-1) ifa(mcr(i),mcr(i+1))==inf ta=A(mcr(i+1),mcr(i))-a(mcr(i+1),mcr(i));
2、else ta=a(mcr(i),mcr(i+1)); end n=min(ta,n);%将最短路径上的最小允许流量提取出来 end fori=1:(size(mcr',1)-1) ifa(mcr(i),mcr(i+1))==inf a(mcr(i+1),mcr(i))=a(mcr(i+1),mcr(i))+n; else a(mcr(i),mcr(i+1))=a(mcr(i),mcr(i+1))-n; end end Mm=Mm+
3、n;%将每次叠代后增加的流量累加,叠代完成时就得到最大流量 fori=1:size(a,1) forj=1:size(a',1) ifi~=j&a(i,j)~=inf ifa(i,j)==A(i,j)%零流弧 c(j,i)=inf; c(i,j)=C(i,j); elseifa(i,j)==0%饱合弧 c(i,j)=inf; c(j,i)=C(j,i);
4、 elseifa(i,j)~=0%非饱合弧 c(j,i)=C(j,i); c(i,j)=C(i,j); end end end end [mcr,mrd]=floyd_mr(c)%进行叠代,得到以花费为权值的最短路径矩阵(mcr)和数值(mrd) n=inf;end%下面是计算最小花费的数值fori=1:size(A,1) forj=1:size(A',1) ifA(i,j)==inf
5、A(i,j)=0; end ifa(i,j)==inf a(i,j)=0; end endendMmr=A-a;%将剩余空闲的流量减掉就得到了路径上的实际流量,行列交点处的非零数值就是两点间路径的实际流量fori=1:size(Mmr,1) forj=1:size(Mmr',1) ifMmr(i,j)~=0 mc=mc+Mmr(i,j)*C(i,j);%最小花费为累加各条路径实际流量与其单位流量花费的乘积 end endend利用福得算法计算最短路径M
6、ATLAB源代码,文件名为floyd_mr.mfunction[mr,mrd]=floyd_mr(a)n=size(a,1);[D,R]=floyd(a);%通过福德算法得到距离矩阵(D)和路径矩阵(R)mrd=D(1,n);%提取从起点1到终点n的最短距离rd=R(1,n);%提取从起点1开始沿最短路径上下一个点的编号(rd)mr=[1,rd];%从起点1开始沿最短路径到rd点的最短路径whilerd~=n%通过循环将最短路径依次提取出来,直到rd点就是最后一个点 mr=[mr,R(rd,n)]; rd=R(rd,n);end福得算法
7、MATLAB源代码,文件名为floyd.mfunction[D,R]=floyd(a)n=size(a,1);D=a;fori=1:n forj=1:n R(i,j)=j; endendR;fork=1:n fori=1:n forj=1:n ifD(i,k)+D(k,j)