【《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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 【Ford-Fulkerson标号算法探析综述 Ford Fulkerson 标号 算法 探析 综述 3400