计算最小费用最大流MATLAB源代码

计算最小费用最大流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))==infta=A(mcr(i+1),mcr(i))-a(mcr(i+1),mcr(i));elseta=a(mcr(i),mcr(i+1));endn=min(ta,n);%将最短路径上的最小允许流量提取出来endfori=1:(size(mcr',1)-1)ifa(mcr(i),mcr(i+1))==infa(mcr(i+1),mcr(i))=a(mcr(i+1),mcr(i))+n;elsea(mcr(i),mcr(i+1))=a(mcr(i),mcr(i+1))-n;endendMm=Mm+n;%将每次叠代后增加的流量累加，叠代完成时就得到最大流量fori=1:size(a,1)forj=1:size(a',1)ifi~=j&a(i,j)~=infifa(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);elseifa(i,j)~=0%非饱合弧c(j,i)=C(j,i);c(i,j)=C(i,j);endendendend[mcr,mrd]=floyd_mr(c)%进行叠代，得到以花费为权值的最短路径矩阵(mcr)和数值(mrd)n=inf;end%下面是计算最小花费的数值fori=1:size(A,1)forj=1:size(A',1)ifA(i,j)==infA(i,j)=0;endifa(i,j)==infa(i,j)=0;endendendMmr=A-a;%将剩余空闲的流量减掉就得到了路径上的实际流量，行列交点处的非零数值就是两点间路径的实际流量fori=1:size(Mmr,1)forj=1:size(Mmr',1)ifMmr(i,j)~=0mc=mc+Mmr(i,j)*C(i,j);%最小花费为累加各条路径实际流量与其单位流量花费的乘积endendend利用福得算法计算最短路径MATLAB源代码,文件名为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福得算法MATLAB源代码,文件名为floyd.mfunction[D,R]=floyd(a)n=size(a,1);D=a;fori=1:nforj=1:nR(i,j)=j;endendR;fork=1:nfori=1:nforj=1:nifD(i,k)+D(k,j)D(i,j)D(i,j)=D(i,k)+D(k,j);R(i,j)=R(i,k);endendendk;D;R;endM=D(1,n);