【《Ford-Fulkerson标号算法探析综述》3400字】.docx

《【《Ford-Fulkerson标号算法探析综述》3400字】.docx》由会员分享，可在线阅读，更多相关《【《Ford-Fulkerson标号算法探析综述》3400字】.docx（10页珍藏版）》请在优知文库上搜索。

1、Ford-Fii1.kerson标号算法分析综述目录Ford-Fu1.kcrson阮号算法分析it述iiI.给发点V,标号(U8)。21.2增广JS程.-21 .更新流31.3算法3I4失现算法的主要而BX62 dof1.u.v)*-061.5Fordau1.kcrson9Kord-Fu1.kei-Son标号算法是一个最经典的基于增广路径策咯的算法，其基本思路是在网络中先找到一个基本的可行流（一般从零流开始）通过标号方法来判断该可行流是否是最大流,如果不是就诳行流量更新调整,如果是的话就可以把直接最大流表示出来。算法主要分为标号和增广调整两个过程：前者通过标号找出网络中是一条增广路径:后者沿若

2、标号过程找到的增广路径来更新路径上的流S.最终能使网络的流量增大。标号可行渔）最大.调推图1.1标号算法过程1.1标号过程1 .给发点内标号（0.+）o第一个数表明该条弧是前向弧还是后向弧，一般用+号表示是正向通，用-号表示反向弧。第二个数是表示对这个点,它的改变量可以是多少。对于发点而言比较特殊.因为设有前向弧或后向弧.所以用。或A表示，而且我们认为它可以源源不断的输入流量,所以改变量是+8。2 .取一个已经标号的点外,采用深度优先遍历对与以相邻的一切未标号的点%按照下列规则进行处理：I）如果有以火为起点的通（/用）是前向弧.且Ofc中那么给终点Uj标号（+%）t其中增量可=min4-知2）

3、如果与相邻接的顶点R之间的弧是反向弧（%/）目是非零流丸,那么给Ui标记为（飞,反向弧上的改变圣是该弧上可以充少的呈.=min（r用3 .重复步骤2,直到汇点力被标号,或者没有顶点可以继续标号,则标号过程结束O如果1被标号.说明在剩余网络中找到了一条噌广链,转到流量调整过程如果打未被标号.程序结束.此时的可行流就是最大添1.2增广过程设5是从源点名到汇点外的一条增广链上所有前向弧剩余流量的最小值.51=minqriy,fvi,vt）*）G是从源点打到汇点外的一条增广链上所有后向犯剩余流量的最小值.S2=min（jy,d（|（vi,vtyE,-min6,521.更新流量ft1.+S增广链迪前向道

4、今工/=/-6增广加的后同通.fii其也强2.清除上述过程的所有标号，再重更标号过程，对新得到的可行流进行重新标号寻找增广路。1.3算法应用生活中许多复杂的问题在经过适当的转换后都可以转化为最大流问题来求解.如生活中的物资运输、物资转运、原油输送等实际问题.最大流问题在其中有很好的应用。下列例子是实际问题的简化：某地区从发点S到收点t的输油网络和现有的输油计划(已给初始流.流至f为3+2+4=9)如图1.2所示，问该网络是否达到或大输油量,如果没有.求出最大的输汨量。标号过程：给发点S标注(0.+8).其邻接点有a、jd,选取点a,对于前向弧(s.a),满足0fxaa-c-b-t图1.4熠广2

5、s-c-e-t对更新后的图1.3重新迸入标号过程,给发点S标注(0,+8),此时前向弧(s.a)流量已达到饱和,所以无法对a标号。检查点c,我们可以给C点标号(+s.1),给C标号(c,1).给t点标号(+e,I).所以.我们又得到一条新的增广信s-c-e-t,沿该增广链进行增广，如图1.4所示，此时流量调整到4+3+4=1Io图1.6增广4s-Xi-e-t继续里豆上述标号过程寻找增广链然后进行流量调整.如图1.5、图1.6。若此时再进行标号，发现对S点和d点标号之后，再也找不到满足标号条件的邻接点明标号过程无法继续进行(图1.7)。汇点t未被你号，则说明此时的流星f=4+3+7=14是该输油

6、网络的最大流累。图1.7最大流与最小割在上图中，标号结束后所有的顶点被划分成两类：已经标号的顶点和未被标号的顶点。己标号点集合Ss.d),未标号点集合Sa,b,C,e.t),所以在求得该网络冠大流的同时我们也得到了该网络的最小割集(S.S)=(s,a),(s,c)、(d,c)、(d,e),最小割的容量=csa+csc+cac+Cde=4+3+3+4=14显然.最小割的容量等于最大流的值。1.4实现算法的主要函数Ford-Fii1.kcrson算法的伪代码如下.FORD-FUI.KERSON(G,$,t)1 foreachedge(u.v)EG2 do11u.v*-O3 11v,u)-O4 wh

7、i1.ethereexistsapathPworkGf5 docf()-nincf(u,v):(u,v)isinp!6 foreachedge(,v)inp7 dof1.u.v11u,vj+cf(p)8 11v,u*-11u,v第13行目的是将各条边的流量初始化为O.从零流开始寻找增广路,最后几行是一直在残留网络Gf中寻找增广路径p.找到后沿若p的方向更新弧的流室.直到最后找不到增广路径,此时得到的流f就是一个最大流.主要函数实现如下,由于篇幅限制,以下只列出几个生要的函数,其他部分代码放在附录中。a)寻找增广路径的函数作用是判断是否存在增广路.若存在,则流量还有增加的可能Oboo1.find

8、Pah(void)memse(ah,0.nodecnn初始化存放路径的数组.nodeent是节点数星b1.visited)MAX,NODE;Hvisited数组记录是否访问过该节点nmscc(visitcd.fa1.sc,nodeent)：/初始化,一开始,所有节点没有被访问Pa1.h1.eng1.h=0;初始化当前的路径长度intsrc=0;/s-t路径的源节点(三)path(pa1.h1.c11g1.hI=src:通过DFS搜索相邻找到s-t路径,如果有一个s-t路径,返叵ItrUCreturn(dfs(src.visited);Ib)深度优先遍历凶数深度优先遍历就像走迷宫,如果想要找到出

9、口,可以从开始的位芭先选择任意一个岔路口,一条路走到黑,直到该岔路无法继续前进。此时原路返回，退回到上一个岔路口,然后选择另一个方向继续一条涔走到黑。重复以上过程,直到找到出口。boo1.dfs(insrc.boo1.*visited)if(三=nodec11t-I)/如果当前是目标.则找到S-I路径return(rue:visitcdsrc=true;or(intdcst=0;dcstO&ivisitcddcst)/找到未访问过的邻近(Pgth+=I;/当前路径长度+1PathIgth=desuU将此相邻添加到S-I路径U继续搜索相邻iR!dfs(dcst,visited)(如果当前的相邻不

10、能到达最终的目标,路径长度减小，因为它提前增加了Pg1.h-=1:continue;继续调查下一个相邻Je1.sereturntrue;/如果当前的相邻能够到达最终的目标Ie1.seif(dcst=nodeent-1”彼有相邻,意味着没有ST涔径returnfa1.se:Ire1.urn0;C)求最小剩余容量的函数该函数在已找到增广路的基础上，遍历其找到该增广路上的流量瓶颈，即还能增加多少流量取决于该路径上所有弧中剩余流量的最小值。intfind_dcha(void)(intde1.taINF;/初始化最小容量ibr(inti=0;iedge(path1.i11pathi+1.JD/如果s-t

11、上边的流量小于当前最小容(Ieka=CdgeIPatMipathi+1.;则更新最小容量Jre1.u11de1.1.a:d)根据s-t路径更新剩余网络的函数根据流虽调整规则,该增广路径上的所有前向弧加上de1.ta.所有后同犯减去de1.tavoidUpdatC(VOid)intsrc=O;inides1.=(inide1.1.a=find_ck1.1.aO;/找到增路径上的冠小流感How+de1.ta;H更新最大流量ibr(inti=O:i(SrC=pa1.hi:dest=pathi+1.:cdgcsrcdcst-=de1.ta：前向弧加上de1.taedgedes(src=de1./后向弧

12、减去de1.ta对于1.3中的问题,应用上述代码,由于程序开始时会把所有的丸上的流量初始化为零,所以在寻找增广涔时是从可行流是零流开始找所有增广路的,最终运行结果如下：增广路1：s-a-b-tde1.ta=1增广路2:S-a-c-b-tde1.ta=3广路3:s-c-b-tde1.ta=1增广路4:s-c-e-b-tde1.ta=2增广路5:s-d-c-c-tde1.ta=3增广路6：s-d-e-tde1.ta=4该网络的最大流至maxI1.ow=141.5Ford-Fu1.kerson算法的缺陷从上面程序运行结果也可以看出.Ford-Fu1.kcrson算法在寻找增广路时具有任意性,并不能保

13、证答次找到的增广路都是最短路径，虽然最终都能求解出最大流,但是在一些特殊的网络,这样任意寻找增广路的策略可能会极其的耗费时间,造成极低的效率。以图1.8为例.初始流是0.弧边上的数字代表该条诞的容量,在这样一个特殊的容量网络中,我们一跟可以看出最大流是9飒(SAU-X)+9999(s-v-t),但Ford-Fu1.kcrson算法如果是不断重复选取s-u-v-t和sv-u-t做为增广路径,每次只能增加I个单位流量，最终需要重复19998次刁能达到最大流量。这是个非常低效的过程,并且当图中弧的容量变成更大的数时,这个劣势将更ZO明显。在大规模网络中.巡免该缺陷的方法是可以考虑将网络中容量过于小的邨的容量增大，或者使用DiniC算法或其他算法替代。图1.8特殊的容量网络由于Ford-Fu1.kerson算法的前提假设为每个边容量c,C是整数,因此边容量是整数时算法是适用的。又因为有理数可以通过扩大倍数