最大流Ford-Fulkerson标号算法步骤及C++源代码

最大流Ford-Fulkerson标号算法基本思想：标号过程来寻找网络中的增广路pred（j）：节点j在可能的增广路中的前一个节点;maxf（j）:沿该可能的增广路到该节点为止可以增广的最大流量.LIST:记录可能的增广路上的节点算法步骤：STEP0.置初始可行流x（如零流）;对节点t标号,即令maxf（t）=任意正值（如1）.STEP1.若maxf（t）0,继续下一步;否则结束.STEP2.取消所有节点jV的标号，即令maxf（j）=0,pred（j）=0；令LIST={s};对节点s标号，即令maxf（s）=充分大的正值.STEP3.如果LIST且maxf（t）=0,继续下一步;否则:(3a)如果t已经有标号(即maxf(t)0)，则找到了一条增广路，沿该增广路对流x进行增广(增广的流量为maxf（t）,增广路可以根据pred回溯方便地得到),转STEP1.(3b)如果t没有标号(即LIST=且maxf(t)=0),转STEP1.STEP4.从LIST中移走一个节点i；寻找从节点i出发的所有可能的增广弧：(4a)对非饱和前向弧（i，j），若节点j没有标号(即pred（j）=0)，则对j进行标号，即令maxf(j)=min{maxf(i),uij-xij}，pred(j)=i,并将j加入LIST中.(4b)对非空反向弧（j，i），若节点j没有标号(即pred(j)=0)，则对j进行标号，令maxf(j)=min{maxf(i),xji}，pred(j)=i,并将j加入LIST中.STEP5.转STEP3.C++源代码：//FordFulkerson.cpp//最大流的FordFulkerson标号算法//copyright:[e-mail],qq:13247899#includestdio.h#includeiostream.h#defineMaxint10000#defineCLength7templateclassTypeTypemin(Typea,Typeb){returnab?a:b;}intisnull(intmlist[],intn){for(intj=1;j=n;j++)if(mlist[j]0)returnj;return0;}voidMaxFlowFF(intn,intCurf[CLength][CLength]){//输出流Curfinti,j,tf=0;for(i=1;i=n;i++)for(j=1;j=n;j++)if(Curf[i][j]!=0){cout顶点i--顶点j流量:Curf[i][j]\n;if(i==1)tf+=Curf[i][j];}printf(\n当前总流量为:%d\n\n,tf);}voidFordFulkerson(intn,intCap[CLength][CLength],intCurf[CLength][CLength]){//s=1,t=n//cap:弧邻接距阵及容量u(i,j)//Curf:当前流量x(i,j)//maxf:增广路中间变量（节点当前流量）//prev:增广路的前导节点//LIST:可能增广节点inti,j;intmaxf[CLength]={Maxint},prev[CLength]={0};intLIST[CLength]={0},Cut[CLength]={0};maxf[n]=1;boolaug=true;while(maxf[n]0)//maxf[n]表示得到最大流{//step2//取消所有节点标号for(j=1;j=n;j++){maxf[j]=0;prev[j]=0;LIST[j]=0;}LIST[1]=1;maxf[1]=Maxint;inttemp;while(true){//step3//判断LIST是否非空,非空返回第一个非空值,空则返回0temp=isnull(LIST,n);//LIST非空且maxf[n]==0if(temp!=0&&maxf[n]==0){//step4//LIST中移走temp，并寻找从temp出发的可能增广弧LIST[temp]=0;for(intk=1;k=n;k++){//非饱和前向弧if(Curf[temp][k]Cap[temp][k]&&prev[k]==0)//{maxf[k]=min(maxf[temp],Cap[temp][k]-Curf[temp][k]);prev[k]=temp;LIST[k]=1;}elseif(Curf[k][temp]0&&prev[k]==0)//非空反向弧{maxf[k]=min(maxf[temp],Curf[k][temp]);prev[k]=temp;LIST[k]=1;}}}else{//step3a,3bif(maxf[n]0)//找到了一条增广路{//对增广当前流Curfintpv=n;while(pv!=1){//非饱和前向弧if(Curf[prev[pv]][pv]Cap[prev[pv]][pv])Curf[prev[pv]][pv]+=maxf[n];elseif(Curf[pv][prev[pv]]0)//非空反向弧Curf[pv][prev[pv]]-=maxf[n];pv=prev[pv];}MaxFlowFF(n,Curf);}break;}}//endofwhile2}//endofwhile1}voidmain(void){//P186T6(b)参考：谢金星《网络优化》intCap[CLength][CLength]={{0,0,0,0,0,0,0},{0,0,3,3,2,0,0},{0,0,0,0,0,4,0},{0,0,0,0,1,0,2},{0,0,1,0,0,0,2},{0,0,0,0,1,0,1},{0,0,0,0,0,0,0},};intCf[CLength][CLength]={0};inti,j;intn=CLength-1;FordFulkerson(n,Cap,Cf);MaxFlowFF(n,Cf);}