求解最大流问题的matlab程序
最大流算法
算法思想:最大流问题实际上是求一可行流{fij}，使得v(f达到最大。若给了一个可行流f，只要判断N中有无关于f的增广路径，如果有增广路径，改进f， 得到一个流量增大的新的可行流；如果没有增广路径，则得到最大流。
1.寻求最大流的标号法(Ford,Fulkerson)
从一个可行流(一般取零流)开始，不断进行以下的标号过程与调整过程，直到找不到关于f的可增广路径为止。
(1)标号过程
在这个过程中，网络中的点分为已标号点和未标号点，已标号点又分为已检查和未检查两种。每个标号点的标号信息表示两个 部分：第一标号表明它的标号从哪一点得到的，以便从vt开始反向追踪找出也增广路径；第二标号是为了表示该顶点是否已检查过。
标号开始时，给vs标上(s，0)，这时vs是标号但末检查的点，其余都是未标号的点，记为(0，0)。
取一个标号而未检查的点vi，对于一切未标号的点vj：
A．对于弧(vi，vj)，若fij
于是vi成为标号且已检查的点，将它的第二个标号记为1。重复上述步骤，一旦vt被标上号，表明得到一条从vi到vt的增广路径p，转入调整过程。
若所有标号都已检查过去，而标号过程进行不下去时，则算法结束，这时的可行流就是最大流。
(2)调整过程
从vt点开始，通过每个点的第一个标号，反向追踪，可找出增广路径P。例如设vt的第一标号为vk(或-vk)，则弧(vk，vt)(或 相应地(vt，vk))是p上弧。接下来检查vk的第一标号，若为vi(或-vi)，则找到(vi，vk)(或相应地(vk，vi))。再检查vi的第一 标号，依此类推，直到vs为止。这时整个增广路径就找到了。在上述找增广路径的同时计算Q：
Q=min{min(cij-fij)，minf*ij}
对流f进行如下的修改：
f'ij = fij+Q (vi，vj)∈ P的前向弧的集合
f'ij = fij-Q (vi，vj)∈ P的后向弧的集合
f'ij = f*ij (vi，vj)不属于P的集合
接着，清除所有标号，对新的可行流f’，重新进入标号过程。
求解最大流问题的matlab程序.(2007-05-22 19:41:06)转载标签： 最大流问题matlab
调用方式：需要将图抽象成矩阵，抽象方法：（i,j,c,f) i---箭尾点，j---箭头点，c---v(i,j)的容量，f---v(i,j)的流量．
主程序
function R=maxliu(R)
while(1)
VV=zengguang(R);
if VV==inf return ;end
R(VV(:,1),4)=R(VV(:,1),4)+VV(:,2)*min(VV(:,3));
end
外部函数1,求图R的增广矩阵
function VV=zengguang(R) %求最短的增广链，要求标号，起点为1，终点为最大
k=size(
R,1);
n=max(R(:,2));
B=R(:,1:2);
for i=1:k;
A(i,1)=R(i,3)-R(i,4);
if R(i,1)~=1&&R(i,2)~=n;
A(i,2)=R(i,4);
else
A(i,2)=0;
end
end
r=1;
for i=1:n
for j=1:k
if (A(j,1)~=0)&&(B(j,1)==i)
V(r,:)=[i,B(j,2)];
r=r+1;
end
if (A(j,2)~=0)&&(B(j,2)==i)
V(r,:)=[i,B(j,1)];
r=r+1;
end
end
end
P=zeros(n,n);
for i=1:size(V,1)
P(V(i,1),V(i,2))=1;
end
Q=dijkstra(P,1,n);
if Q==inf VV=inf; return; end
for i=1:length(Q)-1,
PP=[Q(1,i),Q(1,i+1)];
r1=find(B(:,1)==PP(1,1));
r2=find(B(:,2)==PP(1,2));
rr=intersect(r1,r2);
tt=1;
if isempty(rr)
r1=find(B(:,1)==PP(1,2));
r2=find(B(:,2)==PP(1,1));
rr=intersect(r1,r2);
tt=-1;
end
VV(i,:)=rr;
TT(i,:)=tt;
end
for i=1:size(VV,1)
if TT(i)==1
AA(i,1)=A(VV(i,1),1) ;
end
if TT(i)==-1
AA(i,1)=A(VV(i,1),2) ;
end
end
VV(:,2)=TT;
VV(:,3)=AA;
外部函数2,dijkstra方法求最段路.
function foot=dijkstra(v,x,y) %正权数
m=size(v,1);
T=zeros(m,1); %T的初始化 inf
T=T.^-1;
lmd=T; %lmd的初始化 inf
P=T; %P的初始化 inf
S=zeros(m,1); %S的初始化 (进入S集的点为1)
S(x)=1; %根据本题已知的初始化
P(x)=0; lmd(x)=0;
k=x;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 计算 P
while(1)
a=find(S==0);
aa=find(S==1);
if size(aa,1)==m
break;
end
for j=1:size(a,1)
pp=a(j,1);
if v(k,pp)~=0
if T(pp)>(P(k)+v(k,pp))
T(pp)=(P(k)+v(k,pp));
lmd(pp)=k;
end
end
end
mi=min(T(a));
if mi==inf
break;
else
d=find(T==mi);
d=d(1);
P(d)=mi;
T(d)=inf; %为了避免同样的数字出现两次.
k=d;
S(d)=1;
end
end
if lmd(y)==inf
foot=inf;
return ;
end
foot(1)=y;
g=2; h=y;
while(1)
if h==x
break;
end
foot(g)=lmd(h);
g=g+1;
h=lmd(h);
end
pace=foot;
for i=1:length(foot)
foot(1,i)=pace(1,length(foot)+1-i);
end