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

1、下面的最小费用最大流算法采用的是基于Floyd最短路算法的Ford和Fulkerson迭加算 法，其基本思路为：把各条弧上单位流量的费用看成某种长度，用Floyd求最短路的方法 确定一条自V1至Vn的最短路；再将这条最短路作为可扩充路，用求解最大流问题的方法将 其上的流量增至最大可能值；而这条最短路上的流量增加后，其上各条弧的单位流量的费用 要重新确定，如此多次迭代，最终得到最小费用最大流。本源码由GreenSim团队原创，转 载请注明function f,MinCost,MaxFlow=MinimumCostFlow(a,c,V,s,t)%MinimumCostFlow.m%最小费用最大流算

2、法通用Mat lab函数%基于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);%真实的前向边应该被记住for i=1:Nfor j=1:Nif i=j&c(i,j)

3、=0flag(i,j)=1;%前向边标记flag(j,i)=-1;%反 向边标记endif a(i,j)=infa(i,j)=BV;w(i,j)=BV;%为提高程序的稳健性，以一个有限大数取代无穷大endendendif L(end)BVRE=1;%如果路径长度小于大数，说明路径存在elseRE=0;end%第二步：迭代过程while RE=1&MaxFlow=V%停止条件为达到最大流的预设值或者没有从s到t的最短路 %以下为更新网络结构MinCost1=sum(sum(f.*a);MaxFlow1=sum(f(s,:);f1=f;TS=length(R)-1;%路径经过的跳数LY=zeros

4、(1,TS);%流 量裕度for i=1:TSLY(i)=c(R(i),R(i+1);endmaxLY=min(LY);%流量裕度的最小值，也即最大能够增加的流量for i=1:TSu=R (i);v=R(i+1);if flag(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;%反向链路的流量裕度更新elseif flag(u,v)=1&maxLY=c(u,v)%当这条边为前向边且是饱和边时 w(u,v)=BV;%更新权重值c(u,v)

5、=c(u,v)-maxLY;%更 新流量裕度值w(v,u)=-a(u,v);%反向链路权重更新elseif flag(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);elseif flag(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);if MaxFlow2

6、=VMaxFlow=MaxFlow2;MinCost=MinCost2;L,R=FLOYD(w,s,t);elsef=f1+prop*(f-f1);MaxFlow=V;MinCost=MinCost1+prop*(MinCost2-MinCost1);returnendif L(end)BVRE=1;%如果路径长度小于大数，说明路径存在 elseRE=0;endendfunction L,R=FLOYD(w,s,t) n=size(w,1);D=w;path=zeros(n,n);%以下是标准floyd算法for i=1:nfor j=1:nif D(i,j)=infpath(i,j)=j;endendendfor k=1:nfor i=1:nfor j=1:nif D(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;while 1if s=tL=fliplr(L);L=0,L;r