最大流matlab程序
%n表示节点数，C表示容量矩阵
function [f,wf,No]=MaxFlow(n,C)
for(i=1:n)for(j=1:n)f(i,j)=0;end&
%取初始可行流f为零流
for(i=1:n)No(i)=0;d(i)=0;end& %No,d 记录标号
& No(1)=n+1;d(1)=I %给发点vs 标号
& while(1)pd=1;&& %标号过程
&&& for(i=1:n)if(No(i))&
%选择一个已标号的点vi
for(j=1:n)if(No(j)==0&f(i,j)&C(i,j))&
%对于未给标号的点vj, 当 vivj 为非饱和弧时
No(j)=i;d(j)=C(i,j)-f(i,j);pd=0;&
if(d(j)&d(i))d(j)=d(i);end
elseif(No(j)==0&f(j,i)&0)&&
%对于未给标号的点vj, 当 vjvi 为非零流弧时
No(j)=-i;d(j)=f(j,i);pd=0;
if(d(j)&d(i))d(j)=d(i);end
&&& if(No(n)|pd)end %若收点vt得到标号或者无法标号,
终止标号过程
& if(pd)end %vt 未得到标号, f 已是最大流, 算法终止
& dvt=d(n);t=n;& %进入调整过程, dvt 表示调整量
& while(1)
if(No(t)&0)f(No(t),t)=f(No(t),t)+&&
%前向弧调整
elseif(No(t)&0)f(No(t),t)=f(No(t),t)-end&
%后向弧调整
if(No(t)==1)for(i=1:n)No(i)=0;d(i)=0;&
end& %当t的标号为vs 时, 终止调整过程
&&& t=No(t);&& %继续调整前一段弧上的流f
wf=0;for(j=1:n)wf=wf+f(1,j);end %计算最大流量
f& %显示最大流
wf& %显示最大流量
No& %显示标号, 由此可得最小割, 程序结束
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。MATLAB计算最小费用最大流
用MATLAB计算最小费用最大流的新算法
我在程序文件中所使用的计算最小费用最大流的算法并没有先用福德－富克逊法算出最大流，然后再用对偶法算出最小费用，而是将两种算法结合，最小费用和最大流一起算出。
首先，福德－富克逊法要求对网络增加一个初始可行流，那么不妨设初始可行流为零流。然后再寻找增广链，可以采用对偶法以费用C为权通过福德算法先找从起点至终点的最短路，再以该最短路为增广链调整流量，每一次调整都以矩阵a记录调整的结果。为了能够满足增广链上正向弧非饱合、逆向弧非零流的条件，在每一次以C为权寻找最短路之前，对费用C矩阵进行调整。将正向饱合弧、逆向零流弧对应的C值设为无穷大，非饱合弧的C值设为初始值，这样一来，计算出的最短路径增广链就不会包括正向饱合弧与逆向零流弧了。每一次调整完网络流量之后，网络中的饱合弧、非饱合弧、零流弧会相互转化，因此要对网络中弧所对应的C矩阵再次进行调整。调整的方法就是回到上边：将正向饱合弧、逆向零流弧对应的C值设为无穷大、非饱合弧的C值设为初始值，后再次以C为权通过福德算法寻找最短路径，这样构成一个循环，直至以C为权找不到一条从起点至终点的最短路径为止。找不到最短路径的标志就是福德算法返回从起点至终点的最短路径值为无穷大，此时网络已达最大流。可以见下面：
使用上面的算法，有关最大流可能会提出这样两个问题：
由于是以C为权值寻找的最短路径，那么是不是不能穷尽从起点至终点的路径，如果不能穷尽那就有可能存在没有找到的增广链，还能找到增广链那就不是最大流？
由于这个算法在寻找最短路径前对C矩阵进行了调整，将非增广链的路径排除在寻找范围之外，所以它保证找到的每一条路径都是增广链。而且它每次得到的都是剩余增广链中的最短增广链，而且找到一条就令其花费为无穷大，以至下次寻找到的是次短增广链。而增广链的数量又是有限的，这样一直寻找下去就会将所有增广链穷尽。就好比有1~10十个数字，每次取剩余中的最小数字，取后不放回，最终会将10个数字全部取完。既然增广链可以穷尽，当找不到增广链时，网络流量即达最大流量，这是福德－富克逊法的思想。穷尽之后C矩阵中起点至终点的各条路径值皆为无穷大，因此福德算法会返回从起点到终点的最短路径值为无穷大，可以将此做为退出循环的标志。
会不会已经达到了网络最大流，但该程序还继续循环，导致错误？
程序已经将不符合增广链要求的路径排除在寻找范围之外，于是程序继续循环证明还能找到增加广链，能找到增广链就没有达到最大流。
对于最小费用问题，由于该程序在计算最小费用方面的算法是优先选择费用低的链路，当费用低的链路在保证网络最大流的前提下不能再提供流量时，再转到次低费用的链路上，与“对偶法”的思想一致。因此，最小费用的计算也是正确的。
计算最小费用最大流MATLAB源代码,文件名为mp_mc.m
function[Mm,mc,Mmr]=mp_mc(a,c)
A=a; %各路径最大承载流量矩阵
C=c; %各路径花费矩阵
Mm=0; %初始可行流设为零
mc=0; %最小花费变量
while mrd~=inf %一直叠代到以花费为权值找不到最短路径
i=1:(size(mcr',1)-1)
a(mcr(i),mcr(i+1))==inf
&ta=A(mcr(i+1),mcr(i))-a(mcr(i+1),mcr(i));
&ta=a(mcr(i),mcr(i+1));
&n=min(ta,n);
%将最短路径上的最小允许流量提取出来
i=1:(size(mcr',1)-1)
a(mcr(i),mcr(i+1))==inf
&a(mcr(i+1),mcr(i))=a(mcr(i+1),mcr(i))+n;
&a(mcr(i),mcr(i+1))=a(mcr(i),mcr(i+1))-n;
& & &Mm=Mm+n;
%将每次叠代后增加的流量累加，叠代完成时就得到最大流量
i=1:size(a,1)
j=1:size(a',1)
i~=j&a(i,j)~=inf
a(i,j)==A(i,j) %零流弧
&c(i,j)=C(i,j);
& & &elseif
a(i,j)==0 %饱合弧
&c(j,i)=C(j,i);
& & &elseif
a(i,j)~=0 %非饱合弧
&c(j,i)=C(j,i);
&c(i,j)=C(i,j);
&[mcr,mrd]=floyd_mr(c)
%进行叠代，得到以花费为权值的最短路径矩阵(mcr)和数值(mrd)
%下面是计算最小花费的数值
for i=1:size(A,1)
j=1:size(A',1)
A(i,j)==inf
&A(i,j)=0;
a(i,j)==inf
&a(i,j)=0;
%将剩余空闲的流量减掉就得到了路径上的实际流量，行列交点处的非零数值就是两点间路径的实际流量
for i=1:size(Mmr,1)
j=1:size(Mmr',1)
Mmr(i,j)~=0
&mc=mc+Mmr(i,j)*C(i,j);
%最小花费为累加各条路径实际流量与其单位流量花费的乘积
利用福得算法计算最短路径MATLAB源代码,文件名为floyd_mr.m
function[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点的最短路径
while rd~=n
%通过循环将最短路径依次提取出来，直到rd点就是最后一个点
&mr=[mr,R(rd,n)];
&rd=R(rd,n);
福得算法MATLAB源代码,文件名为floyd.m
function[D,R]=floyd(a)
n=size(a,1);
& for j=1:n
& R(i,j)=j;
& for i=1:n
& & for j=1:n
D(i,k)+D(k,j)&D(i,j)
& D(i,j)=D(i,k)+D(k,j);
& R(i,j)=R(i,k);
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。只需一步，快速开始
扫一扫，访问微社区
查看: 2777|回复: 6|关注: 0
最小费用最大流算法通用Matlab程序
<h1 style="color:# 麦片财富积分
新手, 积分 7, 距离下一级还需 43 积分
关注者： 6
下面的最小费用最大流算法采用的是“基于Floyd最短路算法的Ford和Fulkerson迭加算法”，其基本思路为：把各条弧上单位流量的费用看成某种长度，用Floyd求最短路的方法确定一条自V1至Vn的最短路；再将这条最短路作为可扩充路，用求解最大流问题的方法将其上的流量增至最大可能值；而这条最短路上的流量增加后，其上各条弧的单位流量的费用要重新确定，如此多次迭代，最终得到最小费用最大流。本源码由GreenSim团队原创，转载请注明，有意购买源码或代写相关程序，请与GreenSim团队联系（主页）。
function [f,MinCost,MaxFlow]=MinimumCostFlow(a,c,V,s,t)
%% MinimumCostFlow.m
%&&最小费用最大流算法通用Matlab函数
%% 基于Floyd最短路算法的Ford和Fulkerson迭加算法
% GreenSim团队原创作品，转载请注明
% GreenSim团队主页：
% 欢迎访问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 j=1:N
& && &&&if i~=j&&c(i,j)~=0
& && && && &flag(i,j)=1;%前向边标记
& && && && &flag(j,i)=-1;%反向边标记
& && &&&end
& && &&&if a(i,j)==inf
& && && && &a(i,j)=BV;
& && && && &w(i,j)=BV;%为提高程序的稳健性，以一个有限大数取代无穷大
& && &&&end
if L(end)&BV
& & RE=1;%如果路径长度小于大数，说明路径存在
%% 第二步：迭代过程
while RE==1&&MaxFlow&=V%停止条件为达到最大流的预设值或者没有从s到t的最短路
& & %以下为更新网络结构
& & MinCost1=sum(sum(f.*a));
& & MaxFlow1=sum(f(s,:));
& & TS=length(R)-1;%路径经过的跳数
& & LY=zeros(1,TS);%流量裕度
& & for i=1:TS
& && &&&LY(i)=c(R(i),R(i+1));
& & maxLY=min(LY);%流量裕度的最小值，也即最大能够增加的流量
& & for i=1:TS
& && &&&u=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==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;
& && &&&else
& && &&&end
& & MaxFlow2=sum(f(s,:));
& & MinCost2=sum(sum(f.*a));
& & if MaxFlow2&=V
& && &&&MaxFlow=MaxFlow2;
& && &&&MinCost=MinCost2;
& && &&&[L,R]=FLOYD(w,s,t);
& && &&&f=f1+prop*(f-f1);
& && &&&MaxFlow=V;
& && &&&MinCost=MinCost1+prop*(MinCost2-MinCost1);
& && &&&return
& & if L(end)&BV
& && &&&RE=1;%如果路径长度小于大数，说明路径存在
& && &&&RE=0;
欢迎访问GreenSim团队主页：
欢迎访问GreenSim——算法仿真团队→
function [L,R]=FLOYD(w,s,t)
n=size(w,1);
path=zeros(n,n);
%以下是标准floyd算法
& & for j=1:n
& && &&&if D(i,j)~=inf
& && && && &path(i,j)=j;
& && &&&end
& & for i=1:n
& && &&&for j=1:n
& && && && &if D(i,k)+D(k,j)&D(i,j)
& && && && && & D(i,j)=D(i,k)+D(k,j);
& && && && && & path(i,j)=path(i,k);
& && && && &end
& && &&&end
L=zeros(0,0);
& & if s==t
& && &&&L=fliplr(L);
& && &&&L=[0,L];
& && &&&return
& & L=[L,D(s,t)];
& & R=[R,path(s,t)];
& & s=path(s,t);
欢迎访问GreenSim团队主页：
欢迎访问GreenSim——算法仿真团队→
<h1 style="color:# 麦片财富积分
回复 1# greensim 的帖子
好东西 顶一下！！！！！！！
<h1 style="color:# 麦片财富积分
终于找到好东西了
<h1 style="color:# 麦片财富积分
回复 1# greensim 的帖子
这可是某年数学建模的一片经典论文的算法呢
<h1 style="color:# 麦片财富积分
好东西，找了好久，算法不好找。谢谢！
<h1 style="color:# 麦片财富积分
好东西，很不错。
<h1 style="color:# 麦片财富积分
为什么看不懂。。。无端端冒出的BV和R是什么？
站长推荐 /3
Simulink工具定制实现高效模型验证
MATLAB中文论坛是全球最大的 MATLAB & Simulink 中文社区。用户免费注册会员后，即可下载代码，讨论问题，请教资深用户及结识书籍作者。立即注册加入我们吧！
MATLAB官方社交平台
MATLAB中文论坛微社区matlab能画出最小费用最大流的图形么_百度知道
matlab能画出最小费用最大流的图形么
我有更好的答案
可以采用对偶法以费用C为权通过福德算法先找从起点至终点的最短路，再以该最短路为增广链调整流量，每一次调整都以矩阵a记录调整的结果。为了能够满足增广链上正向弧非饱合、逆向弧非零流的条件，在每一次以C为权寻找最短路之前，对费用C矩阵进行调整。将正向饱合弧、逆向零流弧对应的C值设为无穷大，非饱合弧的C值设为初始值，这样一来，计算出的最短路径增广链就不会包括正向饱合弧与逆向零流弧了。
采纳率：60%
来自团队：
为您推荐：
其他类似问题
&#xe675;换一换
回答问题，赢新手礼包&#xe6b9;
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。