网络流算法介绍与分析ppt课件

1、网络流1;.一些符号和定义一些符号和定义V表示整个图中的一切结点的集合.E表示整个图中一切边的集合.G = (V,E) ,表示整个图.s表示网络的源点,t表示网络的汇点.对于每条边(u,v),有一个容量c(u,v) (c(u,v)=0)假设c(u,v)=0，那么表示(u,v)不存在在网络中。假设原网络中不存在边(u,v)，那么令c(u,v)=0对于每条边(u,v),有一个流量f(u,v).2v1tsv2(2,2)(4,4)(2,4)(0,3)(2,2)一个简单的例子一个简单的例子.网络可网络可以被想象成一些输水的以被想象成一些输水的管道管道.括号内右边的数字括号内右边的数字表示管道的容量表示管

2、道的容量,左边的左边的数字表示这条管道的当数字表示这条管道的当前流量前流量.3网络流的三个性质网络流的三个性质1、容量限制、容量限制: fu,v v2 - v1 - t这条途径经过的弧的流量都添加这条途径经过的弧的流量都添加2,就得到了该就得到了该网络的最大流。网络的最大流。留意到这条途径经过了一条后向弧留意到这条途径经过了一条后向弧:(v2,v1)。假设不设立后向弧，算法就不能发现这条途径。假设不设立后向弧，算法就不能发现这条途径。从本质上说，后向弧为算法纠正本人所犯的错误提供了能够性，它允许算法取消从本质上说，后向弧为算法纠正本人所犯的错误提供了能够性，它允许算法取消先前的错误的行为让先前

3、的错误的行为让2单位的流从单位的流从v1流到流到v2)10为什么要建立后向弧为什么要建立后向弧当然当然,可以把上面说的情况当成特殊情况来处置。但运用后向弧可以使编程简单许可以把上面说的情况当成特殊情况来处置。但运用后向弧可以使编程简单许多多.留意留意,后向弧只是概念上的后向弧只是概念上的,在程序中后向弧与前向弧并无区别在程序中后向弧与前向弧并无区别.11增广路增广路增广路定义：在残量网络中的一条从增广路定义：在残量网络中的一条从s通往通往t的途径，其中恣意一条弧的途径，其中恣意一条弧(u,v)，都有都有ru,v0。绿色的即为一条增广路。绿色的即为一条增广路。v1tsv223242212增广路算

4、法增广路算法增广路算法：每次用增广路算法：每次用BFS找一条最短的增广途径，然后沿着这条途径修正流量值找一条最短的增广途径，然后沿着这条途径修正流量值实践修正的是残量网络的边权。当没有增广路时，算法停顿，此时的流就是实践修正的是残量网络的边权。当没有增广路时，算法停顿，此时的流就是最大流。最大流。下面证明增广路算法的正确性下面证明增广路算法的正确性.13将将f,c,rf,c,r的定义域扩展为点集的定义域扩展为点集(在以后的表达中在以后的表达中,大写字母大写字母X,Y,S,T普通均表示点集普通均表示点集)点集间的流量和点集间的流量和: f(X,Y) =即即:X中的恣意一点与中的恣意一点与Y中的恣

5、意一点组成的一切边上的流量之和中的恣意一点组成的一切边上的流量之和.(边的方向为从边的方向为从X中的结点到中的结点到Y中的结点中的结点)c,r等函数都有类似的定义等函数都有类似的定义.(点集间的容量和、点集间的残量网络容量和点集间的容量和、点集间的残量网络容量和)XxYyyxf),(14结论结论1 11.f(X,X) = 0 (由流量反对称性由流量反对称性)2. f(X,Y) = -f(Y,X) (有流量反对称性有流量反对称性)3.f(X Y,Z) = f(X,Z) + f(Y,Z) (显然显然)4.f(X,Y Z) = f(X,Y) + f(X,Z) (显然显然)15最大流最小割定理最大流最

6、小割定理网络流中这三个条件等价在同一个时辰网络流中这三个条件等价在同一个时辰:1、f是最大流是最大流2、残量网络中找不到增广途径、残量网络中找不到增广途径3、|f| = c(S,T)161 1、f f是最大流是最大流2 2、残量网络中找不到增广途径、残量网络中找不到增广途径3 3、|f| = c(S,T) |f| = c(S,T) 1 - 2证明证明: 显然显然.假设有增广途径假设有增广途径,由于增广途径的容量至少为由于增广途径的容量至少为1,所以用这个增广所以用这个增广途径增广过后的流的流量一定要比途径增广过后的流的流量一定要比f的大的大,这与这与f是最大流矛盾是最大流矛盾.17割的定义割的

7、定义一个割一个割(S,T)由两个点集由两个点集S,T组成组成.S+T = Vs 属于属于 S.t 属于属于 T.提出割的定义提出割的定义,是为后面的证明作铺垫是为后面的证明作铺垫.18结论结论2(2(点集总流量为零点集总流量为零) )不包含s和t的点集,于它相关联的边上的流量之和为0.证明: f(X,V) = = (由流量平衡) = 0 ),( XxYyyxfXx019结论结论3 3恣意割的流量等于整个网络的流量恣意割的流量等于整个网络的流量.证明证明: f(S,T) = f(S,V) f(S,S) (由辅助定理由辅助定理1) = f(S,V) (由辅助定理由辅助定理1) = f(S,V) +

8、 f(S s,V) (同上同上) = f(s,V) (由辅助定理由辅助定理2) = |f| (由由|f|的定义的定义)20结论结论4 4网络的流量小于等于恣意一个割的容量.(留意这个与辅助定理3的区别.这里是容量)即|f| = c(S,T)证明: |f| = f(S,T) = (由定义) 3证明证明: 定义定义S = s v | 在残量网络中在残量网络中s到到v有一条途径有一条途径 ; T = V- S. 那么那么 (S,T) 是一个割是一个割.|f| = f(S,T) (由辅助定理由辅助定理3)而且而且,r(S,T) = 0. 假设不为假设不为0,那么在残量网络中那么在残量网络中, 两个集合

9、间必定有边相连两个集合间必定有边相连,设在设在S的一端为的一端为v,在在T的一端为的一端为u. 那么那么,s就可以经过就可以经过v到达到达u,那么根据那么根据S的定义的定义,u就应该在就应该在S中中.矛盾矛盾. 所以所以,|f| = f(S,T) = c(S,T) r(S,T) = c(S,T)1 1、f f是最大流是最大流2 2、残量网络中找不到增广途径、残量网络中找不到增广途径3 3、|f| = c(S,T) |f| = c(S,T) 223 - 1证明证明: |f| 0),那么那么|f|+d一定不能满一定不能满足上面的条件足上面的条件.1 1、f f是最大流是最大流2 2、残量网络中找不

10、到增广途径、残量网络中找不到增广途径3 3、|f| = c(S,T) |f| = c(S,T) 23增广路算法的正确性增广路算法的正确性假设假设 最大流最小割定理不能从最大流最小割定理不能从2推出推出3,那么存在这样一种能够性那么存在这样一种能够性: 虽然找不到增广途径了虽然找不到增广途径了,但由于前面的错误决策但由于前面的错误决策,导致导致f还没有到达最大流还没有到达最大流,却不能却不能经过修正当前流来得到最大流经过修正当前流来得到最大流.但由于最大流最小割定理的三个条件相互等价但由于最大流最小割定理的三个条件相互等价(1-2,2-3,3-1), 一个流是最大流一个流是最大流当且仅当它没有增

11、广途径当且仅当它没有增广途径.24增广路算法的效率增广路算法的效率设设n = |V|, m = |E|每次增广都是一次每次增广都是一次BFS,效率为效率为O(m)所以所以,总共的时间复杂度为总共的时间复杂度为O(m*f*)其中其中f*为增广次数为增广次数.怎样求怎样求f*?25f f* *对于随机数据对于随机数据,f*的值与的值与n比较接近比较接近.当当m不太大也不太小时不太大也不太小时,f*的值较大的值较大.(我出随机数据的方法是我出随机数据的方法是:固定地为源点和汇点连上一些边固定地为源点和汇点连上一些边,然后随机生成中间的边然后随机生成中间的边.中间的边保证边的两个端点的编号相差不太大中

12、间的边保证边的两个端点的编号相差不太大.这与不少标题转成网络流后构成的这与不少标题转成网络流后构成的图类似图类似)26f f* *的实际上界的实际上界思索每一次增广思索每一次增广,至少有一条边的至少有一条边的r(u,v)值等于增广途径的流量值等于增广途径的流量.称这些边为临界边称这些边为临界边.增广之后增广之后,这条临界边就在残量网络中消逝这条临界边就在残量网络中消逝.假设一条临界边对应一次增广假设一条临界边对应一次增广(现实上很难到达这样现实上很难到达这样),令每条边成为临界边的次数令每条边成为临界边的次数为为k(u,v),那么有那么有f* = O(m*k).k的上界的上界?27k k的上界

13、的上界假设要让一条曾经的临界边假设要让一条曾经的临界边(u,v)再次成为临界边再次成为临界边,那么必需有一条增广途径包含边那么必需有一条增广途径包含边(v,u).由由于每次增广之后临界边就消逝于每次增广之后临界边就消逝,要让他再次成为临界边至少要让他再次在残量网络中出现要让他再次成为临界边至少要让他再次在残量网络中出现,即即(v,u)要被增广要被增广.结合上面的结论可以证明结合上面的结论可以证明,当算法取的增广路总是残量网络中的最短路当算法取的增广路总是残量网络中的最短路,恣意一条边成为临恣意一条边成为临界边的次数至多为界边的次数至多为n/2-1.因此因此,增广路算法的效率为增广路算法的效率为

14、O(f*m) = O(km2) = O(nm2). (这只是个上界这只是个上界,普通情况是达普通情况是达不到的不到的)备注中为增广路算法我的代码实现。数组备注中为增广路算法我的代码实现。数组u是残量网络的容量。是残量网络的容量。28预流推进算法预流推进算法下面将引见一个更直观且时间效率更优的算法下面将引见一个更直观且时间效率更优的算法.29;.一个直观的想法一个直观的想法假设给他一个网络流假设给他一个网络流,让他手算出它的最大流让他手算出它的最大流,他会怎样算他会怎样算?普通人都会尝试着从源点出发普通人都会尝试着从源点出发,让每条边的流量尽能够得大让每条边的流量尽能够得大,然后一点点往汇点推然

15、后一点点往汇点推,直到遇到一条比较窄的弧直到遇到一条比较窄的弧,原先的流量过不去了原先的流量过不去了,这才减少原先的流量这才减少原先的流量.30v1tsv2(0,2)(4,4)(0,4)(3,3)(0,2)例例2.一个直观的想法一个直观的想法大致的思绪：从源点出发，逐渐推进。大致的思绪：从源点出发，逐渐推进。称当前形状下不满足流量平衡的结点为称当前形状下不满足流量平衡的结点为“溢出溢出的结点的结点.(对于结点对于结点u,f(V,u) 0 )令令e(u) = f(V,u),称为称为u点的赢余，直观地描画，点的赢余，直观地描画，就是就是“流入的比流出的多多少。流入的比流出的多多少。e(v1)=4,

16、e(v2)=3。不断将溢出的结点中的赢余。不断将溢出的结点中的赢余往后继点推进往后继点推进,直到赢余都聚集在直到赢余都聚集在t.31v1tsv2(2,2)(4,4)(0,4)(3,3)(2,2)假设多推了一些流量假设多推了一些流量, 我们可以再把它推回我们可以再把它推回来来. (如如e(v2)=3,但这但这3个单位的赢余曾经没地个单位的赢余曾经没地方去了方去了,只能推回来只能推回来.)(沿着后向弧沿着后向弧)这副图是这副图是原网络而不是残量网络原网络而不是残量网络,因此没把后项弧画因此没把后项弧画出来出来)例例2.2.一个直观的想法一个直观的想法32v1tsv2(2,2)(4,4)(0,4)(

17、3,3)(2,2)程序没有全局观程序没有全局观?!?!此时此时e(v2)=3.正确的回推法是往正确的回推法是往(v2,s)推推1,往往(v2,v1)推推2,然后使得这然后使得这2个单位的赢余可以从个单位的赢余可以从(v1,t)推到推到t上。上。但程序没有全局观但程序没有全局观,它万一往它万一往(v2,s)推了推了3个单个单位怎样办位怎样办?我们总不能尝试一切的能够性吧我们总不能尝试一切的能够性吧,那样就变成搜索了那样就变成搜索了.33引导机制引导机制把流推错能够导致产生的流不是最大流把流推错能够导致产生的流不是最大流.我们需求有一个能引导流的推进方向的机制我们需求有一个能引导流的推进方向的机制

18、,当它发现我们先前的推进是错误的时当它发现我们先前的推进是错误的时候候,能沿着正确的后向弧回推回来能沿着正确的后向弧回推回来.由于建立了后向弧由于建立了后向弧,正推与回推在程序中并无却别，都是在推残量网络中的一条边正推与回推在程序中并无却别，都是在推残量网络中的一条边.34高度标号的引导作用高度标号的引导作用高度标号就是这样的一个引导机制高度标号就是这样的一个引导机制.我们规定我们规定,假设一个结点溢出了假设一个结点溢出了,那么他的多余的流量只能流向高度标号比本人低那么他的多余的流量只能流向高度标号比本人低的结点的结点.(“水往低处流水往低处流)当然当然,高度标号不能够事先知道往哪些方向推才是

19、正确的高度标号不能够事先知道往哪些方向推才是正确的.它将按情况动态改动本它将按情况动态改动本人的值人的值,从而正确地引导流向从而正确地引导流向.35重标号操作重标号操作当一个结点有赢余当一个结点有赢余(溢出了溢出了), 周围却没有高度比它低的结点时候周围却没有高度比它低的结点时候,我们就用重标号我们就用重标号操作使它的标号上升到比周围最低的结点略高一点操作使它的标号上升到比周围最低的结点略高一点,使他的赢余能流出去使他的赢余能流出去.赢余千万不能困在某个结点里赢余千万不能困在某个结点里.对于恣意一个非源非汇的结点，有赢余就意味着它对于恣意一个非源非汇的结点，有赢余就意味着它不满足流量平衡，也就

20、意味着整个网络流不是一个真正合法的网络流。不满足流量平衡，也就意味着整个网络流不是一个真正合法的网络流。36重标号操作重标号操作对于例对于例2的这种情况的这种情况,v2中过多的赢余最终会沿着中过多的赢余最终会沿着(v2,v1)、(v2,s)流回去流回去(虽然他们虽然他们一开场流错了方向一开场流错了方向,但后来又被回推但后来又被回推,等于说是被矫正了等于说是被矫正了)。只需当非源非汇的结点中的赢余全部流到汇点或流回源点后，这个流才重新合法。只需当非源非汇的结点中的赢余全部流到汇点或流回源点后，这个流才重新合法。37高度函数高度函数高度函数高度函数h(v)前往一个前往一个v的高度标号。的高度标号。

21、高度函数有三个根本条件：高度函数有三个根本条件：h(s) = |V|h(t) = 0对于对于Ef(残量网络残量网络)中的每一条边中的每一条边(u,v),(r(u,v)0)h(u) 0,那就表示从那就表示从u到到v还可以添加流量还可以添加流量,那那h(u)就应该比就应该比h(v)高才对高才对.确实确实,我们后面还将规定我们后面还将规定,只需在只需在h(u)h(v)的时候才干运的时候才干运用推进操作用推进操作(将一个结点的盈余推进到另一个结点的操作将一个结点的盈余推进到另一个结点的操作).而高度函数为了满足其而高度函数为了满足其合法性合法性,还要满足上述的这三个条件还要满足上述的这三个条件.后面我

22、们将利用这三个条件证明预流推进算后面我们将利用这三个条件证明预流推进算法的正确性。法的正确性。38高度函数的条件的本质高度函数的条件的本质h(u) 0，r(u,v)0, h(u) = h(v)+1u溢出，溢出，(u,v)在残量网络中，两者的高度差为在残量网络中，两者的高度差为1推进量为推进量为e(u)与与r(u,v)的最小值。的最小值。推进时同时更改相关的推进时同时更改相关的r与与e的值。的值。41推进操作推进操作 伪代码伪代码Procedure Push(u,v)X min e(u), r(u,v) Dec(r(u,v), x)Inc(r(v,u), x)Dec(e(u), x) Inc(e

23、(v), x)42重标号操作重标号操作运用对象：运用对象： 一个结点一个结点u运用条件：运用条件：结点结点u溢出；残量网络中周围一切的点的高度都不比它低。溢出；残量网络中周围一切的点的高度都不比它低。Relabel(u)u(u) = min h(v) | (u,v)是残量网络总的边是残量网络总的边 + 1运用了重标号操作后运用了重标号操作后,至少存在一个至少存在一个(u,v)满足满足h(u)=h(v)+1.43预流初始化预流初始化(Init-Preflow)(Init-Preflow)一开场的时候，我们要让和源点一开场的时候，我们要让和源点s相关连的边都尽能够的充溢。但由于相关连的边都尽能够的

24、充溢。但由于s没有溢出，没有溢出，不符合推进操作的运用条件，我们需求另写一段初始化的代码。还得做的一件事不符合推进操作的运用条件，我们需求另写一段初始化的代码。还得做的一件事是初始化高度函数是初始化高度函数.h(s) = n h(v) = 0 (vs)对于一切与对于一切与s相关联的点相关联的点v，Inc( e(v), c(s,v) ), Dec( e(s), c(s,v) )将边将边(s,v)反向，变成反向，变成(v,s) 在残量网络中。在残量网络中。初始化过后，初始化过后，e(s)变成负数。变成负数。44结论结论5 5对于一个溢出的结点，两个关键操作推进和重标号能且只能运用一个。对于一个溢出

25、的结点，两个关键操作推进和重标号能且只能运用一个。证明：对于一个溢出的结点证明：对于一个溢出的结点u,和一切与他相关联的点和一切与他相关联的点v( (u,v)在残量网络中存在在残量网络中存在),必然有必然有h(u) = h(v) + 1.(由高度函数的定义由高度函数的定义).根据根据v分成两种情况分成两种情况:1).一切一切v都有都有h(u)h(v)+1 2).至少存在一个至少存在一个v,使得使得h(u)=h(v)+1. 而而1)2)互为否命题互为否命题,不能同时成立或同时不成立不能同时成立或同时不成立.那么那么1)对应重标号对应重标号,2)对应推进对应推进,两者必能运用一个两者必能运用一个且

26、只能运用一个且只能运用一个.45普通的预流推进算法普通的预流推进算法由辅助定理由辅助定理5,得到了一个普通的预流推进算法得到了一个普通的预流推进算法.(好短好短)Init-PreflowWhile 存在一个溢出的结点存在一个溢出的结点选一个结点选一个结点,运用相应的关键操作运用相应的关键操作(推进或重标号推进或重标号).当不存在溢出结点时当不存在溢出结点时(s,t不算不算),算法终了算法终了,得到一个可行流得到一个可行流,并且还是最大流并且还是最大流.46预流推进算法的正确性预流推进算法的正确性预流只是不满足流量平衡预流只是不满足流量平衡,网络流的前两条性质网络流的前两条性质-容量限制和反对称

27、性它还是满足容量限制和反对称性它还是满足的的.当不存在溢出结点时当不存在溢出结点时,流量平衡也满足了流量平衡也满足了.所以所以,当算法终了时当算法终了时,我们得到一个可行流我们得到一个可行流(合法流合法流).为什么他是一个最大流呢为什么他是一个最大流呢?下面先看几个结论下面先看几个结论:47结论结论6(6(结点高度永不下降结点高度永不下降) )只需重标号操作能更改结点的高度标号只需重标号操作能更改结点的高度标号.在重标号操作运用前在重标号操作运用前,必有必有h(u) = h(u) + 1.所以所以,在重标号操作后在重标号操作后,高度标号至少高度标号至少+1.48结论结论7 7在算法执行过程中在

28、算法执行过程中,h一直是一个合法的高度函数一直是一个合法的高度函数.(满足那三个条件满足那三个条件)1).调查一个被重标号的结点调查一个被重标号的结点u.设设(u,v)存在于存在于Ef,v0是一切是一切v中中h最小的一个最小的一个. H(u)=h(v0)+1,满足满足h(u)=h(v0)+1,而而h(v0) = h(v),所以所以 h(u)=h(v)+1.设设(w,u)存在于存在于Ef,那么那么h(w)=h(u)+1=h(u)+1.仍旧满足仍旧满足.49结论结论7 7在算法执行过程中在算法执行过程中,h一直是一个合法的高度函数一直是一个合法的高度函数.(满足那三个条件满足那三个条件)2).调查

29、一个被推进的边调查一个被推进的边(u,v).(v,u)能够是在这次推进之后才出如今能够是在这次推进之后才出如今Ef中中.它的出现使得新增了一个限制条它的出现使得新增了一个限制条件件:h(v)=h(u)+1.不过不过,这显然是满足的这显然是满足的,由于推进操作的运用条件是由于推进操作的运用条件是h(u)=h(v)+1.那么那么h(v)=h(u)-1 = h(u)+150结论结论8(8(预流中无增广路预流中无增广路) )当当h是一个合法的高度函数时是一个合法的高度函数时,Gf中一直不存在增广路中一直不存在增广路.(这个定理展现了这个定理展现了h的条件的的条件的重要性和巧妙性重要性和巧妙性)证明证明

30、:假设存在增广路假设存在增广路p=(v0,v1,vk),其中其中v0=s,vk=t.由于增广途径中无反复由于增广途径中无反复点点,k+1=|V|,即即k|V|.51结论结论8(8(预流中无增广路预流中无增广路) )fkkffEvvEvvEvv),(),(),(121101)()(1)()(1)()(12110kkvhvhvhvhvhvh相加得相加得:h(s)=h(t)+k=0+k=k而而k|V|,所以所以h(s)|V|.而根据定义而根据定义,h(s)=|V|.矛盾矛盾.52预流推进算法的正确性预流推进算法的正确性当有溢出结点时当有溢出结点时,根据结论根据结论5,必定可以在它上面施加一个操作必定

31、可以在它上面施加一个操作.当算法停顿时当算法停顿时,由于无溢出结点由于无溢出结点,所以当前流是一个合法流所以当前流是一个合法流,而根据结论而根据结论8,Gf中一直中一直不存在增广路不存在增广路.根据最大流最小割定理根据最大流最小割定理,当当Gf中不存在增广路时中不存在增广路时,当前流是最大流当前流是最大流.(算法执行了一半时虽然也没有增广路算法执行了一半时虽然也没有增广路,但由于它不是一个合法流但由于它不是一个合法流,前面的诸多定理前面的诸多定理都不成立都不成立).算法的最优性的保证者算法的最优性的保证者:对于一切在对于一切在Ef中的中的(v,u), 均有均有h(v)0h(u) = h(v)+

32、1可行边集可行边集Ef,h:一切由可行弧组成的集合。一切由可行弧组成的集合。可行网络可行网络Gf,h = (V,Ef,h)56结论结论9,109,10结论结论9:可行网络中无环可行网络中无环.(和结论和结论8的证明类似的证明类似,弄一堆式子然后叠加一下弄一堆式子然后叠加一下,导出矛盾导出矛盾)结论结论10:推进操作永远不会新增可行弧推进操作永远不会新增可行弧,却能够使原有的可行弧消逝却能够使原有的可行弧消逝.(根据可行弧的根据可行弧的定义显然定义显然)57结论结论1111在在u被重标号之后被重标号之后:1).至少有一条可行弧分开至少有一条可行弧分开u. 显然显然.设设v0是是u的邻居中的邻居中

33、h值最小的那一个值最小的那一个,那么那么(u,v0)必定是一条可行弧必定是一条可行弧.2).不能够有可行弧进入不能够有可行弧进入u. 假设有一条假设有一条(w,u).那么那么h(w) = h(u) + 1.根据辅助定理根据辅助定理6,relabel操作至少将结点操作至少将结点的的h+1,所以所以h(w) h(u) + 1.根据高度函数必需满足的条件根据高度函数必需满足的条件,(w,u)在在relabel前不在前不在Ef中中.而而relabel操作只改动可行网络不改动残量网络操作只改动可行网络不改动残量网络,(w,u)不能够在不能够在relabel前存在前存在于于Ef而之后就不存在而之后就不存在

34、.58当前弧当前弧每个结点有一个邻居列表和有一个每个结点有一个邻居列表和有一个“当前弧的指针当前弧的指针,保管当前检查到邻居列表中保管当前检查到邻居列表中的哪一条弧了。初始化时的哪一条弧了。初始化时,“当前弧指向与该结点相连的第一条边当前弧指向与该结点相连的第一条边.邻居列表保管邻居列表保管的是一切能够成为可行弧的弧的是一切能够成为可行弧的弧.当再次调用检查操作时当再次调用检查操作时,可以从上一次检查了一半的地方继续检查可以从上一次检查了一半的地方继续检查.详细请看下面检查操作的伪代码详细请看下面检查操作的伪代码:59检查操作检查操作Check(u)While e(u)0 doIf curre

35、nt(u)degree(u) then /当没有可行弧可以推进当没有可行弧可以推进,该结点却仍旧有赢余时该结点却仍旧有赢余时,重标号重标号.Relabel(u)Current(u) = 1ElseIf (u,current(u) 是一条可行弧是一条可行弧 then Push(u,current(u) /push了之后就不能添加了之后就不能添加 current(u)的值的值.由于这假设是一次非饱和推进由于这假设是一次非饱和推进,那再下一次检查时还是可以沿着这条弧做推进那再下一次检查时还是可以沿着这条弧做推进.Else Inc(current(u)60当前弧的正确性当前弧的正确性Current是全

36、局变量是全局变量,当某次当某次Check操作终了时他的值并没有被清空操作终了时他的值并没有被清空.比如结点比如结点u有有10个邻居个邻居,上次检查到第上次检查到第7个个,那再一次那再一次Check(u)的时候就只需从第的时候就只需从第7个开场检查就可以了。个开场检查就可以了。为什么再一次检查的时候不要检查第为什么再一次检查的时候不要检查第1-6条边了条边了?能否证明在再一次检查的时候他能否证明在再一次检查的时候他们一定不是可行弧们一定不是可行弧?61当前弧的正确性当前弧的正确性在在relabel-to-front算法中算法中,relabel只被只被Check调用调用.当当“当前弧挪动时当前弧挪

37、动时,挪动前它指向的那条弧一定是不可行的挪动前它指向的那条弧一定是不可行的.而推进操作不能发明而推进操作不能发明可行弧可行弧.只需只需relabel可以可以.两次两次Check之间没有之间没有relabel操作操作.所以原先的不可行的弧所以原先的不可行的弧在第二次在第二次Check之前不断是不可行的之前不断是不可行的.62Relabel-to-frontRelabel-to-frontInit-Preflow初始化结点初始化结点(除除s,t)列表列表L(任何顺序均可任何顺序均可)令一切令一切u,Current(u) = 1u HeadLWhile u nil doOld-height h(u)

38、Check(u)If h(u) old-height then 将将u移到移到L首部首部/假设假设h(u)比原先的比原先的h高了高了,阐明被阐明被relabel,移到队首移到队首.u next(u)63图例图例 ( (初始形状初始形状. .结点下方数字为赢余结点下方数字为赢余,N,N显示的是邻居列表显示的是邻居列表,N,N中红色的是当前弧指针中红色的是当前弧指针所在的位置所在的位置.) .)S-26x12y14z0t06543210(12/12)(14/14)(0/16)(0/7)(0,5)(0,8)(0,10)LxyzN ssxyxyzztt64图例图例:x:x被检查并重标号被检查并重标号,

39、 ,并被提到并被提到L L的首部的首部( (等于没提等于没提). ).留意当前弧的指针移到了留意当前弧的指针移到了t. xt. x的的一切赢余推给了一切赢余推给了y y和和t. t.S-26x0y19z0t76543210(12/12)(14/14)(7/16)(0/7)(5,5)(0,8)(0,10)LxyzN ssxyxyzztt65图例图例 :y :y正在被检查正在被检查. .将将8 8单位的赢余推给单位的赢余推给z z之后还是有剩余之后还是有剩余. .S-26x0y11z8t76543210(12/12)(14/14)(7/16)(0/7)(5,5)(8,8)(0,10)LxyzN s

40、sxyxyzztt66图例图例 : :一次必需把赢余全部推光一次必需把赢余全部推光. .所以所以y y被重标号被重标号, ,当前弧指针从头开场查找当前弧指针从头开场查找, ,找到找到(y,x)(y,x)这条可行弧之后进展推进这条可行弧之后进展推进. .实践上是把多推的赢余还给了实践上是把多推的赢余还给了x.x.由于由于h(u)=h(v)+1h(u)=h(v)+1的保证的保证, ,它没有把赢余错推给它没有把赢余错推给s.s.S-26x5y6z8t76543210(12/12)(14/14)(7/16)(0/7)(0,5)(8,8)(0,10)LxyzN ssxyxyzztt67图例图例:y:y还

41、是有赢余还是有赢余. .当当前弧挪动到另局列表的尾部时当当前弧挪动到另局列表的尾部时,y,y再一次被重标号再一次被重标号, ,并把赢余还并把赢余还给给s.s.检查终了检查终了,y,y被提到被提到L L列表的首部列表的首部. .S-20 x5y0z8t76543210(12/12)(8/14)(7/16)(0/7)(0,5)(8,8)(0,10)LyxzN ssxxyyzztt68图例图例: :检查检查x.x.留意留意x x的当前弧指针曾经指在的当前弧指针曾经指在t t上了上了. x. x把赢余推给把赢余推给t. ut. u指针直接后移指针直接后移.( .(由于由于x x没有被重标号没有被重标号

42、) )S-20 x0y0z8t126543210(12/12)(8/14)(12/16)(0/7)(0,5)(8,8)(0,10)LyxzN ssxxyyzztt69图例图例:z:z被检查并被提到列表首部被检查并被提到列表首部. .S-20 x0y0z0t206543210(12/12)(8/14)(12/16)(0/7)(0,5)(8,8)(8,10)LzyxN xssyxytzzt70图例图例:u:u指针从指针从y y开场向后挪动开场向后挪动, ,直到队尾也没有发现可以检查的结点直到队尾也没有发现可以检查的结点( (只需溢出的结点才只需溢出的结点才干被检查干被检查). ).算法终了算法终了

43、. .S-20 x0y0z0t206543210(12/12)(8/14)(12/16)(0/7)(0,5)(8,8)(8,10)LzyxN xssyxytzzt t71relabel-to-frontrelabel-to-front的正确性的正确性前面我们曾经证明了普通预流推进算法的正确性了前面我们曾经证明了普通预流推进算法的正确性了.因此因此,如今只需证明如今只需证明,在在relabel-to-front算法终了时算法终了时,普通预流推进算法的终了条件也正好被满足普通预流推进算法的终了条件也正好被满足-即没有溢出的即没有溢出的结点结点.72结论结论11:L11:L一直拓扑有序一直拓扑有序对

44、于对于G上的可行网络上的可行网络Gf,h,列表列表L中的结点一直坚持拓扑有序性中的结点一直坚持拓扑有序性.一开场的时候一开场的时候,列表中一切结点列表中一切结点(s,t不在列表中不在列表中)的高度均为的高度均为0,不存在高度差不存在高度差,所以不所以不存在可行弧存在可行弧.这时列表显然拓扑有序这时列表显然拓扑有序.一个结点被一个结点被relabel之后之后,就被提到列表的首部就被提到列表的首部.根据辅助定理根据辅助定理11,relabel之后没有可之后没有可行弧进入结点行弧进入结点,但有可行弧分开结点但有可行弧分开结点,所以将结点提到列表首部仍旧使列表满足拓所以将结点提到列表首部仍旧使列表满足

45、拓扑有序扑有序.推进操作不能发明可行弧推进操作不能发明可行弧,因此与列表的拓扑有序性无关因此与列表的拓扑有序性无关.73结论结论1212L中指针中指针u之前的结点全部是非溢出结点之前的结点全部是非溢出结点.当一个结点被检查之后当一个结点被检查之后,它必定没有赢余它必定没有赢余,因此将因此将u指针后移不影响上面的性质指针后移不影响上面的性质.它本人没有赢余了它本人没有赢余了,但它却能够将赢余推给了他人但它却能够将赢余推给了他人.假设推给在假设推给在L中位置在它后面的中位置在它后面的结点不要紧结点不要紧.但假设它把赢余推给了在本人之前的结点呢但假设它把赢余推给了在本人之前的结点呢?由于由于L拓扑有

46、序拓扑有序,他假设把赢余推给了排在本人前面的结点他假设把赢余推给了排在本人前面的结点,那么必定发生了那么必定发生了relabel操作操作.而假设有而假设有relabel,那么它曾经被提到列表的首部了那么它曾经被提到列表的首部了.性质依然满足性质依然满足.这就是算法名这就是算法名:relabel-to-front的由来的由来.74Relabel-to-frontRelabel-to-front根据普通的预流推进算法根据普通的预流推进算法,当没有溢出结点时算法就终了并得到一个最大流当没有溢出结点时算法就终了并得到一个最大流.而而relabel-to-front算法的终了条件是算法的终了条件是u指针

47、指向指针指向L队列尾部队列尾部.根据辅助定理根据辅助定理12,u以前的结点均非溢出结点以前的结点均非溢出结点.所以当所以当u指向尾部时指向尾部时,一切的结点均没一切的结点均没有溢出有溢出.另外可以证明另外可以证明,算法的复杂度为算法的复杂度为O(n3).75Highest-relabelHighest-relabel还可以改良还可以改良.阅历阐明阅历阐明,总是检查高度标号最大的结点，会有比较好的效率总是检查高度标号最大的结点，会有比较好的效率.于是对于是对Relabel-to-front进展了一点小修正进展了一点小修正,得到了得到了highest-relabel算法算法.76分块的分块的L L

48、列表列表可以证明可以证明,恣意结点的最大的间隔标号为恣意结点的最大的间隔标号为2n-1.将将L列表分成列表分成2n个块个块,第第1块保管一切高度为块保管一切高度为0的点的点,第第i+1块保管高度为块保管高度为I的一切结点的一切结点.从最后一块开场往前找从最后一块开场往前找,发现一个不为空的块就把这个块里的结点全部检查掉发现一个不为空的块就把这个块里的结点全部检查掉.假假设有元素被重标号了设有元素被重标号了,那就将他挪动到新的块里那就将他挪动到新的块里,并从那个新的块的前面开场继续并从那个新的块的前面开场继续往下查找往下查找.77分块的分块的L L列表列表对于可行网络对于可行网络,分块分块L列表

49、是拓扑有序的列表是拓扑有序的.由于可行弧由于可行弧(u,v)要求要求h(u) = h(v) + 1,即只需从标号高的结点指向标号低的结点即只需从标号高的结点指向标号低的结点.既既只需从后面的块里的结点指向前面的块里的结点只需从后面的块里的结点指向前面的块里的结点.所以所以,这种分块方法依然坚持了这种分块方法依然坚持了整个列表的拓扑有序性整个列表的拓扑有序性.因此因此,算法终了时没有溢出的结点算法终了时没有溢出的结点.因此该算法是正确的因此该算法是正确的.78分块分块L L列表的实现列表的实现假设用链表，可以只占用假设用链表，可以只占用O(n)的空间。在内存不紧张的情况下，也完全可以用无的空间。

50、在内存不紧张的情况下，也完全可以用无序数组，时间效率不比链表差序数组，时间效率不比链表差,虽然空间是虽然空间是O(n2)的的.无序数组在删除的时候，可以用无序数组在删除的时候，可以用:Delete(i)ai anDec(n)79更多的改良更多的改良回想一下上面两个算法的正确性回想一下上面两个算法的正确性:1).h是一个合法的高度函数是一个合法的高度函数 Gf不存在增广路不存在增广路2).同一结点同一结点h值保证递增值保证递增 重标号后没有可行弧进入结点重标号后没有可行弧进入结点 列表列表L永远拓扑有序永远拓扑有序Relabel-to-front(highest-relabel)算法正确算法正确.也就是说也就是说,只需满足只需满足1).2).两条两条,h的值详细怎样变化并不重要的值详细怎样变化并不重要.80更多的改良更多的改良可以发现可以发现,每当重标号操作被执行每当重标号操作被执行,该结点的当前弧的位置就被重置该结点的当前弧的位置就被重置,同时这个结点同时这个结点被往前提被往前提,然后这个结点后面的结点又全部得被检查一遍然后这个结点后面的结点又全部得被检查一遍.也就是说也就是说,每次重标