用MATLAB求解最大流问题

function [f,wf,No]=MaxFlowMinCut_Me(n,C)

% 利用Ford--Fulkerson 标号法求最大流算法的MATLAB 程序代码

% f %显示最大流

% wf %显示最大流量

% No %显示标号, 由此可此芹悄得最小割

% n 节点个数

% C %弧容量

% Example:

% n=8

% C=[0 5 4 3 0 0 0 0

%0 0 0 0 5 3 0 0

%0 0 0 0 0 3 2 0

%0 0 0 0 0 0 2 0

%0 0 0 0 0 0 0 4

%0 0 0 0 0 0 0 3

%0 0 0 0 0 0 0 5

%0 0 0 0 0 0 0 0]

% [f,wf,No]=MaxFlowMinCut_Me(n,C)

for(i=1:n)for(j=1:n)f(i,j)=0endend %取初始可行流f 为零流

for(i=1:n)No(i)=0d(i)=0end %No,d 记录标号

while(1)

No(1)=n+1d(1)=Inf%给发点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)=id(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)=-id(j)=f(j,i)pd=0

if(d(j)>d(i))d(j)=d(i)endendendendend

if(No(n)|pd)breakendend %若收点vt 得到标号或者无法标号, 终止标号过程

if(pd)breakend %vt 未得到标号, f 已是最大流, 算法终止

dvt=d(n)t=n%进入调整过程, dvt 表示调整量

while(1)

if(No(t)>0)f(No(t),t)=f(No(t),t)+dvt%前向弧调整

elseif(No(t)<0)f(No(t),t)=f(No(t),t)-dvtend %后向弧调整

if(No(t)==1)for(i=1:n)No(i)=0d(i)=0endbreakend %当t 的标号为vs 时, 终止调整过程

t=No(t)endend%继续调整前一段弧上的流f

wf=0for(j=1:n)wf=wf+f(1,j)end

end

现在给的这段程序是网上的，我也没跑，先把网址给你，希望对你有帮助！

http://bbs.elecfans.com/jishu_207409_1_1.html

程序：

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)%真实的前向边应该被记住

for i=1: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

end

end

if L(end)<BV

RE=1%如果路径长度小于大数，说明路径存在

else

RE=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(1,TS)%流量裕度

for i=1:TS

LY(i)=c(R(i),R(i+1))

end

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

end

MaxFlow2=sum(f(s,:))

MinCost2=sum(sum(f.*a))

if MaxFlow2<=V

MaxFlow=MaxFlow2

MinCost=MinCost2

[L,R]=FLOYD(w,s,t)

else

f=f1+prop*(f-f1)

MaxFlow=V

MinCost=MinCost1+prop*(MinCost2-MinCost1)

return

end

if L(end)<BV

RE=1%如果路径长度小于大数，说明路径存在

else

RE=0

end

end

function [L,R]=FLOYD(w,s,t)

n=size(w,1)

D=w

path=zeros(n,n)

%以下是标准floyd算法

for i=1:n

for j=1:n

if D(i,j)~=inf

path(i,j)=j

end

end

end

for k=1:n

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

end

end

L=zeros(0,0)

R=s

while 1

if s==t

L=fliplr(L)

L=[0,L]

return

end

L=[L,D(s,t)]

R=[R,path(s,t)]

s=path(s,t)

end

---