资源描述：
《最大流算法MATLAB.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、从一个可行流f开始,求最大流的Ford--Fulkerson标号算法的基本步骤：⑴标号过程①给发点vs以标号(+,+∞),ds=+∞.②选择一个已标号的点x,对于x的所有未给标号的邻接点y,按下列规则处理：当yx∈E,且fyx＞0时,令dy=min{fyx,dx},并给y以标号(x−,dy).当xy∈E,且fxy＜Cxy时,令dy=min{Cxy−fxy,dx},并给y以标号(x+,dy).③重复②直到收点vt被标号或不再有点可标号时为止.若vt得到标号,说明存在一条可增广链,转⑵调整过程;若vt未得到标号,标号过程已无法进行时,说明f已经是最
2、大流.⑵调整过程④决定调整量d=dvt,令u=vt.⑤若u点标号为(v+,du),则以fvu+d代替fvu;若u点标号为(v−,du),则以fvu−d代替fvu.⑥若v=vs,则去掉所有标号转⑴重新标号;否则令u=v,转⑤.算法终止后,令已有标号的点集为S,则割集(S,Sc)为最小割,从而Wf=C(S,Sc).例1求图6-19所示网络的最大流.利用Ford--Fulkerson标号法求最大流算法的MATLAB程序代码如下：n=8;C=[0543000000005300000003200000002000000004000000030000000
3、500000000];%弧容量for(i=1:n)for(j=1:n)f(i,j)=0;end;end%取初始可行流f为零流for(i=1:n)No(i)=0;d(i)=0;end%No,d记录标号while(1)No(1)=n+1;d(1)=Inf;%给发点vs标号while(1)pd=1;%标号过程for(i=1:n)if(No(i))%选择一个已标号的点vifor(j=1:n)if(No(j)==0&f(i,j)4、f(d(j)>d(i))d(j)=d(i);endelseif(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;end;end;end;endif(No(n)
5、pd)break;end;end%若收点vt得到标号或者无法标号,终止标号过程if(pd)break;end%vt未得到标号,f已是最大流,算法终止dvt=d(n);t=n;%进入调整过程,dvt表示调整量while(1)if(No(t)>0)f(N
6、o(t),t)=f(No(t),t)+dvt;%前向弧调整elseif(No(t)<0)f(No(t),t)=f(No(t),t)-dvt;end%后向弧调整if(No(t)==1)for(i=1:n)No(i)=0;d(i)=0;end;break;end%当t的标号为vs时,终止调整过程t=No(t);end;end;%继续调整前一段弧上的流fwf=0;for(j=1:n)wf=wf+f(1,j);end%计算最大流量f%显示最大流wf%显示最大流量No%显示标号,由此可得最小割,程序结束
