【Ford-Fulkerson标号算法探析综述3400字】

Ford-Fulkerson标号算法分析综述目录TOC\o"1-2"\h\u4191Ford-Fulkerson标号算法分析综述 1327451.1标号过程 2258971.给发点vs标号（0,+∞）。 2246371.2增广过程 2233511.更新流量 380871.3算法应用 312131.4实现算法的主要函数 620312dof[u,v]←0 6189681.5Ford-Fulkerson算法的缺陷 10 Ford-Fulkerson标号算法是一个最经典的基于增广路径策略的算法，其基本思路是在网络中先找到一个基本的可行流（一般从零流开始）通过标号方法来判断该可行流是否是最大流，如果不是就进行流量更新调整，如果是的话就可以把直接最大流表示出来。算法主要分为标号和增广调整两个过程：前者通过标号找出网络中是一条增广路径；后者沿着标号过程找到的增广路径来更新路径上的流量，最终能使网络的流量增大。标号标号可行流最大流可行流最大流调整调整图1.1标号算法过程1.1标号过程给发点vs标号（0,+∞）。第一个数表明该条弧是前向弧还是后向弧，一般用+号表示是正向弧，用-号表示反向弧。第二个数是表示对这个点，它的改变量可以是多少。对于发点而言比较特殊，因为没有前向弧或后向弧，所以用0或Δ表示，而且我们认为它可以源源不断的输入流量，所以改变量是+∞。取一个已经标号的点vi，采用深度优先遍历对与vi相邻的一切未标号的点如果有以vi为起点的弧（vi,vj）是前向弧，且0≤fij≤cij，那么给终点vj标号(+vi，∂j)，其中增量∂j如果与vi相邻接的顶点vj之间的弧是反向弧（vj,vi）且是非零流弧，那么给vi标记为(-vi,∂j)，反向弧上的改变量是该弧上可以减少的量，重复步骤2，直到汇点vt被标号，或者没有顶点可以继续标号，则标号过程结束。

如果vt被标号，说明在剩余网络中找到了一条增广链，转到流量调整过程

如果1.2增广过程设 δ1是从源点vs到汇点vδ1=min{cij-fij，∂i|δ2是从源点vs到汇点 δ2=min{fij，∂i| δ=min{δ1更新流量令fij'=清除上述过程的所有标号，再重复标号过程，对新得到的可行流进行重新标号寻找增广路。1.3算法应用生活中许多复杂的问题在经过适当的转换后都可以转化为最大流问题来求解，如生活中的物资运输、物资转运、原油输送等实际问题，最大流问题在其中有很好的应用。下列例子是实际问题的简化： 某地区从发点s到收点t的输油网络和现有的输油计划（已给初始流，流量f为3+2+4=9）如图1.2所示，问该网络是否达到最大输油量，如果没有，求出最大的输油量。图1.2输油网络标号过程：给发点s标注（0，+∞）,其邻接点有a、c、d，选取点a，对于前向弧（s，a），满足0≤fsa≤csa，δa=min{4-3，+∞}=1，所以给点a标号为（+s，1）。继续深度优先遍历，找到a的邻接点b，前向弧（a，b）是饱和弧，不满足标号条件，再检查a的邻接点c，前向弧（a，c）是非饱和弧，δc=min{3-2，1}=1，故给c点标号（+a，1）。同理，给b点标号（+c，1），给t标号（+b，1），现在，收点t得到了标号，说明在剩余网络中存在一条增广链，标号结束。调整过程：δ=min{δa，δc，令fij'=调整结果如图1.3，此时流量调整到4+2+4=10。图1.3增广链μ1s->a->c->b->t图1.4增广μ对更新后的图1.3重新进入标号过程，给发点s标注（0，+∞）,此时前向弧（s，a）流量已达到饱和，所以无法对a标号。检查点c，我们可以给c点标号（+s，1），给e标号（+c，1），给t点标号（+e，1），所以，我们又得到一条新的增广链s->c->e->t，沿该增广链进行增广，如图1.4所示，此时流量调整到4+3+4=11。图1.5增广μ3s->d->c->e->t图1.6增广μ继续重复上述标号过程寻找增广链然后进行流量调整，如图1.5、图1.6。若此时再进行标号，发现对s点和d点标号之后，再也找不到满足标号条件的邻接点v，标号过程无法继续进行（图1.7）。汇点t未被标号，则说明此时的流量f=4+3+7=14是该输油网络的最大流量。图1.7最大流与最小割在上图中，标号结束后所有的顶点被划分成两类：已经标号的顶点和未被标号的顶点。已标号点集合S{s，d}，未标号点集合S{a，b，c，e，t}，所以在求得该网络最大流的同时我们也得到了该网络的最小割集(S,S)={（s，a）、（s，c）、（d，c）、（d，e）}，最小割的容量=csa+csc+cdc+1.4实现算法的主要函数Ford-Fulkerson算法的伪代码如下，FORD-FULKERSON(G,s,t)1foreachedge(u,v)∈E[G]2dof[u,v]←03f[v,u]←04whilethereexistsapathpfromstotintheresidualnetworkGf5docf(p)←min{cf(u,v):(u,v)isinp}6foreachedge(u,v)inp7dof[u,v]←f[u,v]+cf(p)8f[v,u]←-f[u,v]第1~3行目的是将各条边的流量初始化为0，从零流开始寻找增广路，最后几行是一直在残留网络Gf主要函数实现如下，由于篇幅限制，以下只列出几个重要的函数，其他部分代码放在附录中。寻找增广路径的函数作用是判断是否存在增广路，若存在，则流量还有增加的可能。boolfindPath(void){memset(path,0,nodecnt); //初始化存放路径的数组，nodecnt是节点数量boolvisited[MAX_NODE];//visited数组记录是否访问过该节点memset(visited,false,nodecnt);//初始化，一开始，所有节点没有被访问pathLength=0; //初始化当前的路径长度intsrc=0; //s-t路径的源节点(s)path[pathLength]=src;//通过DFS搜索相邻找到s-t路径，如果有一个s-t路径，返回truereturn(dfs(src,visited)); }深度优先遍历函数深度优先遍历就像走迷宫，如果想要找到出口，可以从开始的位置先选择任意一个岔路口，一条路走到黑，直到该岔路无法继续前进。此时原路返回，退回到上一个岔路口，然后选择另一个方向继续一条路走到黑。重复以上过程，直到找到出口。booldfs(intsrc,bool*visited){if(src==nodecnt-1)//如果当前是目标(t)，则找到s-t路径returntrue;visited[src]=true;for(intdest=0;dest<nodecnt;dest++)//搜索与src相邻的{if(edge[src][dest]>0&&!visited[dest])//找到未访问过的邻近{pathLength+=1; //当前路径长度+1path[pathLength]=dest;//将此相邻添加到s-t路径//继续搜索相邻if(!dfs(dest,visited)){//如果当前的相邻不能到达最终的目标，路径长度减小，因为它提前增加了pathLength-=1;continue;//继续调查下一个相邻}else{returntrue;//如果当前的相邻能够到达最终的目标}}elseif(dest==nodecnt-1)//没有相邻，意味着没有s-t路径returnfalse;}return0;}求最小剩余容量的函数该函数在已找到增广路的基础上，遍历其找到该增广路上的流量瓶颈，即还能增加多少流量取决于该路径上所有弧中剩余流量的最小值。intfind_delta(void){intdelta=INF;//初始化最小容量for(inti=0;i<pathLength-1;i++){if(delta>edge[path[i]][path[i+1]])//如果s-t上边的流量小于当前最小容量{delta=edge[path[i]][path[i+1]];//则更新最小容量}}returndelta;}根据s-t路径更新剩余网络的函数根据流量调整规则，该增广路径上的所有前向弧加上delta，所有后向弧减去deltavoidupdate(void){intsrc=0;intdest=0;intdelta=find_delta();//找到增广路径上的最小流量flow+=delta;//更新最大流量for(inti=0;i<pathLength-1;i++){src=path[i];dest=path[i+1];edge[src][dest]-=delta;//前向弧加上deltaedge[dest][src]+=delta;//后向弧减去delta}}对于1.3中的问题，应用上述代码，由于程序开始时会把所有的弧上的流量初始化为零，所以在寻找增广路时是从可行流是零流开始找所有增广路的，最终运行结果如下：增广路1：s->a->b->tdelta=1增广路2：s->a->c->b->tdelta=3增广路3：s->c->b->tdelta=1增广路4：s->c->e->b->tdelta=2增广路5：s->d->c->e->tdelta=3增广路6：s->d->e->tdelta=4该网络的最大流量maxflow=141.5Ford-Fulkerson算法的缺陷从上面程序运行结果也可以看出，Ford-Fulkerson算法在寻找增广路时具有任意性，并不能保证每次找到的增广路都是最短路径，虽然最终都能求解出最大流，但是在一些特殊的网络中，这样任意寻找增广路的策略可能会极其的耗费时间，造成极低的效率。以图1.8为例，初始流是0，弧边上的数字代表该条弧的容量，在这样一个特殊的容量网络中，我们一眼可以看出最大流是9999（s->u->t）+9999（s->v->t），但Ford-Fulkerson算法如果是不断重复选取s->u->v->t和s->v->u->t做为增广路径，每次只能增加1个单位流量，最终需要重复19998次才能达到最大流量。这是个非常低效的过程，并且当图中弧的容量变成更大的数时，这