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

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

2、yd最短路算法的 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:N|for j=1:Nif i=j &&c

3、(i,j)=Oflag(i,j)=1;%前向边标记flag(j,i)=-1;%反向边标记end if a(i,j)=inf a(i,j)=BV;w(i,j)=BV;%为提高程序的稳健性，以一个有限大数取代无穷大endendif L(e nd)<BVRE=1;%如果路径长度小于大数，说明路径存在elseRE=0;end%第二步：迭代过程while RE=1 &&MaxFlow<=V%亭止条件为达到最大流的预设值或者没有从s到t的最短路%以下为更新网络结构Mi nCost仁sum(sum(f.*a);MaxFIow 仁 sum(f(s,:);f1=f;TS=le ngt

4、h(R)-1;% 路径经过的跳数LY=zeros(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 &&maxLY<c(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-

5、c(u,v)%当这条边为前向边且是饱和边时w(u,v)-BV;%更新权重值c(u,v)-c(u,v)-maxLY;%更新流量裕度值w(v,u)-a(u,v);%反向链路权重更新elseif flag(u,v)=-1 &&maxLY<c(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;e

6、lseendendMaxFlow2=sum(f(s,:);Mi nCost2=sum(sum(f.*a);if MaxFlow2<=VMaxFlow=MaxFlow2;Mi nCost=Mi nCost2;L,R=FLOYD(w,s,t);elsef=f1+prop*(f-f1);MaxFlow=V;Min Cost=Mi nCost1+prop*(Mi nCost2-Mi nCost1);returnendif L(e nd)<BVRE=1;%如果路径长度小于大数，说明路径存在elseRE=0;endendfun ctio n 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)=i nfpath(i,j)=j;endendfor k=1: nfor i=1:nfor j=1: nif D(i,k)+D(k,j)<D