最小费用最大流问题matlab程序

下面的最小费用最大流算法采用的是“基于Floyd最短路算法的Ford和Fulkerson迭加算法”，其基本思路为：把各条弧上单位流量的费用看成某种长度，用Floyd求最短路的方法确定一条自V1至Vn的最短路；再将这条最短路作为可扩充路，用求解最大流问题的方法将其上的流量增至最大可能值；而这条最短路上的流量增加后，其上各条弧的单位流量的费用要重新确定，如此多次迭代，最终得到最小费用最大流。本源码由GreenSim团队原创，转载请注明function[f,MinCost,MaxFlow]=MinimumCostFlow(a,c,V,s,t)%%MinimumCostFlow.m%最小费用最大流算法通用Matlab函数%%基于Floyd最短路算法的Ford和Fulkerson迭加算法%GreenSim团队原创作品，转载请注明%%输入参数列表%a单位流量的费用矩阵%c链路容量矩阵%V最大流的预设值，可为无穷大%s源节点%t目的节点%%输出参数列表%f链路流量矩阵%MinCost最小费用%MaxFlow最大流量%%第一步：初始化N=size(a,1);%节点数目f=zeros(N,N);%流量矩阵，初始时为零流MaxFlow=sum(f(s,:));%最大流量，初始时也为零flag=zeros(N,N);%真实的前向边应该被记住fori=1:Nforj=1:Nifi~=j&&c(i,j)~=0flag(i,j)=1;%前向边标记flag(j,i)=-1;%反向边标记endifa(i,j)==infa(i,j)=BV;w(i,j)=BV;%为提高程序的稳健性，以一个有限大数取代无穷大endendendifL(end)BVRE=1;%如果路径长度小于大数，说明路径存在elseRE=0;end%%第二步：迭代过程whileRE==1&&MaxFlow=V%停止条件为达到最大流的预设值或者没有从s到t的最短路%以下为更新网络结构MinCost1=sum(sum(f.*a));MaxFlow1=sum(f(s,:));f1=f;TS=length(R)-1;%路径经过的跳数LY=zeros(1,TS);%流量裕度fori=1:TSLY(i)=c(R(i),R(i+1));endmaxLY=min(LY);%流量裕度的最小值，也即最大能够增加的流量fori=1:TSu=R(i);v=R(i+1);ifflag(u,v)==1&&maxLYc(u,v)%当这条边为前向边且是非饱和边时f(u,v)=f(u,v)+maxLY;%记录流量值w(u,v)=a(u,v);%更新权重值c(v,u)=c(v,u)+maxLY;%反向链路的流量裕度更新elseifflag(u,v)==1&&maxLY==c(u,v)%当这条边为前向边且是饱和边时w(u,v)=BV;%更新权重值c(u,v)=c(u,v)-maxLY;%更新流量裕度值w(v,u)=-a(u,v);%反向链路权重更新elseifflag(u,v)==-1&&maxLYc(u,v)%当这条边为反向边且是非饱和边时w(v,u)=a(v,u);c(v,u)=c(v,u)+maxLY;w(u,v)=-a(v,u);elseifflag(u,v)==-1&&maxLY==c(u,v)%当这条边为反向边且是饱和边时w(v,u)=a(v,u);c(u,v)=c(u,v)-maxLY;w(u,v)=BV;elseendendMaxFlow2=sum(f(s,:));MinCost2=sum(sum(f.*a));ifMaxFlow2=VMaxFlow=MaxFlow2;MinCost=MinCost2;[L,R]=FLOYD(w,s,t);elsef=f1+prop*(f-f1);MaxFlow=V;MinCost=MinCost1+prop*(MinCost2-MinCost1);returnendifL(end)BVRE=1;%如果路径长度小于大数，说明路径存在elseRE=0;endendfunction[L,R]=FLOYD(w,s,t)n=size(w,1);D=w;path=zeros(n,n);%以下是标准floyd算法fori=1:nforj=1:nifD(i,j)~=infpath(i,j)=j;endendendfork=1:nfori=1:nforj=1:nifD(i,k)+D(k,j)D(i,j)D(i,j)=D(i,k)+D(k,j);path(i,j)=path(i,k);endendendendL=zeros(0,0);R=s;while1ifs==tL=fliplr(L);L=[0,L];returnendL=[L,D(s,t)];R=[R,path(s,t)];s=path(s,t);end