信息學(xué)奧賽網(wǎng)絡(luò)流算法介紹與分析

1、網(wǎng)絡(luò)流杭州學(xué)軍中學(xué)杭州學(xué)軍中學(xué) 魏越閩魏越閩一些符號(hào)和定義一些符號(hào)和定義V表示整個(gè)圖中的所有結(jié)點(diǎn)的集合.E表示整個(gè)圖中所有邊的集合.G = (V,E) ,表示整個(gè)圖.s表示網(wǎng)絡(luò)的源點(diǎn),t表示網(wǎng)絡(luò)的匯點(diǎn).對(duì)于每條邊(u,v),有一個(gè)容量c(u,v) (c(u,v)=0)如果c(u,v)=0，則表示(u,v)不存在在網(wǎng)絡(luò)中。如果原網(wǎng)絡(luò)中不存在邊(u,v)，則令c(u,v)=0對(duì)于每條邊(u,v),有一個(gè)流量f(u,v).v1tsv2(2,2)(4,4)(2,4)(0,3)(2,2)一個(gè)簡(jiǎn)單的一個(gè)簡(jiǎn)單的例子例子.網(wǎng)絡(luò)可網(wǎng)絡(luò)可以被想象成以被想象成一些輸水的一些輸水的管道管道.括號(hào)內(nèi)括號(hào)內(nèi)右邊的數(shù)字右邊

2、的數(shù)字表示管道的表示管道的容量容量,左邊的左邊的數(shù)字表示這數(shù)字表示這條管道的當(dāng)條管道的當(dāng)前流量前流量.網(wǎng)絡(luò)流的三個(gè)性質(zhì)網(wǎng)絡(luò)流的三個(gè)性質(zhì)1、容量限制容量限制: fu,v v2 - v1 - t這條路徑這條路徑經(jīng)過(guò)的弧的流量都增加經(jīng)過(guò)的弧的流量都增加2,就得到了該網(wǎng)絡(luò)的最就得到了該網(wǎng)絡(luò)的最大流。大流。注意到這條路徑經(jīng)過(guò)了一條后向弧注意到這條路徑經(jīng)過(guò)了一條后向弧:(v2,v1)。如果不設(shè)立后向弧，算法就不能發(fā)現(xiàn)這條路徑。如果不設(shè)立后向弧，算法就不能發(fā)現(xiàn)這條路徑。從本質(zhì)上說(shuō)，后向弧為算法糾正自己所犯的錯(cuò)從本質(zhì)上說(shuō)，后向弧為算法糾正自己所犯的錯(cuò)誤提供了可能性，它允許算法取消先前的錯(cuò)誤誤提供了可能性，它允

3、許算法取消先前的錯(cuò)誤的行為（讓的行為（讓2單位的流從單位的流從v1流到流到v2)為什么要建立后向弧為什么要建立后向弧當(dāng)然當(dāng)然,可以把上面說(shuō)的情況當(dāng)成特殊情況可以把上面說(shuō)的情況當(dāng)成特殊情況來(lái)處理。但使用后向弧可以使編程簡(jiǎn)單來(lái)處理。但使用后向弧可以使編程簡(jiǎn)單許多許多.注意注意,后向弧只是概念上的后向弧只是概念上的,在程序中后向在程序中后向弧與前向弧并無(wú)區(qū)別弧與前向弧并無(wú)區(qū)別.增廣路增廣路增廣路定義：增廣路定義：在殘?jiān)跉埩烤W(wǎng)絡(luò)中的一條從量網(wǎng)絡(luò)中的一條從s通往通往t的路徑，其的路徑，其中任意一條弧中任意一條弧(u,v)，都有，都有ru,v0。綠色的即為一條增綠色的即為一條增廣路。廣路。v1tsv223

4、2422增廣路算法增廣路算法增廣路算法：每次用增廣路算法：每次用BFS找一條最找一條最短的增廣路徑，然后沿著這條路徑短的增廣路徑，然后沿著這條路徑修改流量值（實(shí)際修改的是殘量網(wǎng)修改流量值（實(shí)際修改的是殘量網(wǎng)絡(luò)的邊權(quán)）。當(dāng)沒(méi)有增廣路時(shí)，算絡(luò)的邊權(quán)）。當(dāng)沒(méi)有增廣路時(shí)，算法停止，此時(shí)的流就是最大流。法停止，此時(shí)的流就是最大流。下面證明增廣路算法的正確性下面證明增廣路算法的正確性.將將f,c,rf,c,r的定義域擴(kuò)展為點(diǎn)集的定義域擴(kuò)展為點(diǎn)集(在以后的敘述中在以后的敘述中,大寫字母大寫字母X,Y,S,T一般均表示一般均表示點(diǎn)集點(diǎn)集)點(diǎn)集間的流量和點(diǎn)集間的流量和: f(X,Y) =即即:X中的任意一點(diǎn)與中

5、的任意一點(diǎn)與Y中的任意一點(diǎn)組成的所中的任意一點(diǎn)組成的所有邊上的流量之和有邊上的流量之和.(邊的方向?yàn)閺倪叺姆较驗(yàn)閺腦中的結(jié)點(diǎn)中的結(jié)點(diǎn)到到Y(jié)中的結(jié)點(diǎn)中的結(jié)點(diǎn))c,r等函數(shù)都有類似的定義等函數(shù)都有類似的定義.(點(diǎn)集間的容量和、點(diǎn)集間的容量和、點(diǎn)集間的殘量網(wǎng)絡(luò)容量和點(diǎn)集間的殘量網(wǎng)絡(luò)容量和)XxYyyxf),(結(jié)論結(jié)論1 11.f(X,X) = 0 (由流量反對(duì)稱性由流量反對(duì)稱性)2. f(X,Y) = -f(Y,X) (有流量反對(duì)稱性有流量反對(duì)稱性)3.f(X Y,Z) = f(X,Z) + f(Y,Z) (顯然顯然)4.f(X,Y Z) = f(X,Y) + f(X,Z) (顯然顯然)最大流最小割

6、定理最大流最小割定理網(wǎng)絡(luò)流中這三個(gè)條件等價(jià)（網(wǎng)絡(luò)流中這三個(gè)條件等價(jià)（在同一個(gè)時(shí)刻）:1、f是最大流是最大流2、殘量網(wǎng)絡(luò)中找不到增廣路徑、殘量網(wǎng)絡(luò)中找不到增廣路徑3、|f| = c(S,T)1 1、f f是最大流是最大流2 2、殘量網(wǎng)絡(luò)中找不到增廣路徑、殘量網(wǎng)絡(luò)中找不到增廣路徑3 3、|f| = c(S,T) |f| = c(S,T) 1 - 2證明證明: 顯然顯然.假設(shè)有增廣路徑假設(shè)有增廣路徑,由于增廣路徑的容量至少為由于增廣路徑的容量至少為1,所以所以用這個(gè)增廣路徑增廣過(guò)后的流的流用這個(gè)增廣路徑增廣過(guò)后的流的流量肯定要比量肯定要比f(wàn)的大的大,這與這與f是最大流矛是最大流矛盾盾.割的定義割的定

7、義一個(gè)割一個(gè)割(S,T)由兩個(gè)點(diǎn)集由兩個(gè)點(diǎn)集S,T組成組成.S+T = Vs 屬于屬于 S.t 屬于屬于 T.提出割的定義提出割的定義,是為后面的證明作鋪墊是為后面的證明作鋪墊.結(jié)論結(jié)論2(2(點(diǎn)集總流量為零點(diǎn)集總流量為零) )不包含不包含s和和t的點(diǎn)集的點(diǎn)集,于它相關(guān)聯(lián)的邊上的流量之于它相關(guān)聯(lián)的邊上的流量之和為和為0.證明證明: f(X,V) = = (由流量平衡由流量平衡) = 0 ),( XxYyyxfXx0結(jié)論結(jié)論3 3任意割的流量等于整個(gè)網(wǎng)絡(luò)的流量任意割的流量等于整個(gè)網(wǎng)絡(luò)的流量.證明證明: f(S,T) = f(S,V) f(S,S) (由輔助定理由輔助定理1) = f(S,V) (

8、由輔助定理由輔助定理1) = f(S,V) + f(S s,V) (同上同上) = f(s,V) (由輔助定理由輔助定理2) = |f| (由由|f|的定義的定義)結(jié)論結(jié)論4 4網(wǎng)絡(luò)的流量小于等于任意一個(gè)割的網(wǎng)絡(luò)的流量小于等于任意一個(gè)割的容量容量.(注意注意這個(gè)與輔助定理這個(gè)與輔助定理3的區(qū)別的區(qū)別.這里是容量這里是容量)即即|f| = c(S,T)證明證明: |f| = f(S,T) = (由定義由定義) 3證明證明: 定義定義S = s v | 在殘量網(wǎng)絡(luò)中在殘量網(wǎng)絡(luò)中s到到v有一條路徑有一條路徑 ; T = V- S. 則則 (S,T) 是一個(gè)割是一個(gè)割.|f| = f(S,T) (由輔

9、助定理由輔助定理3)而且而且,r(S,T) = 0. 假設(shè)不為假設(shè)不為0,則在殘量網(wǎng)絡(luò)中則在殘量網(wǎng)絡(luò)中, 兩個(gè)集合間必定有邊相連兩個(gè)集合間必定有邊相連,設(shè)在設(shè)在S的一端為的一端為v,在在T的一端為的一端為u. 那么那么,s就可以通過(guò)就可以通過(guò)v到達(dá)到達(dá)u,那么根那么根據(jù)據(jù)S的定義的定義,u就應(yīng)該在就應(yīng)該在S中中.矛盾矛盾. 所以所以,|f| = f(S,T) = c(S,T) r(S,T) = c(S,T)1 1、f f是最大流是最大流2 2、殘量網(wǎng)絡(luò)中找不到增廣路徑、殘量網(wǎng)絡(luò)中找不到增廣路徑3 3、|f| = c(S,T) |f| = c(S,T) 3 - 1證明證明: |f| 0),那么那

10、么|f|+d肯定不能滿肯定不能滿足上面的條件足上面的條件.1 1、f f是最大流是最大流2 2、殘量網(wǎng)絡(luò)中找不到增廣路徑、殘量網(wǎng)絡(luò)中找不到增廣路徑3 3、|f| = c(S,T) |f| = c(S,T) 增廣路算法的正確性增廣路算法的正確性如果如果 最大流最小割定理不能從最大流最小割定理不能從2推出推出3,那那么存在這樣一種可能性么存在這樣一種可能性: 盡管找不到增廣路徑了盡管找不到增廣路徑了,但由于前面的錯(cuò)但由于前面的錯(cuò)誤決策誤決策,導(dǎo)致導(dǎo)致f還沒(méi)有到達(dá)最大流還沒(méi)有到達(dá)最大流,卻不能卻不能通過(guò)修改當(dāng)前流來(lái)得到最大流通過(guò)修改當(dāng)前流來(lái)得到最大流.但由于最大流最小割定理的三個(gè)條件互但由于最大流最

11、小割定理的三個(gè)條件互相等價(jià)相等價(jià)(1-2,2-3,3-1), 一個(gè)流是最大一個(gè)流是最大流流當(dāng)且僅當(dāng)它沒(méi)有增廣路徑它沒(méi)有增廣路徑.增廣路算法的效率增廣路算法的效率設(shè)設(shè)n = |V|, m = |E|每次增廣都是一次每次增廣都是一次BFS,效率為效率為O(m)所以所以,總共的時(shí)間復(fù)雜度為總共的時(shí)間復(fù)雜度為O(m*f*)其中其中f*為增廣次數(shù)為增廣次數(shù).怎么求怎么求f*?f f* *對(duì)于隨機(jī)數(shù)據(jù)對(duì)于隨機(jī)數(shù)據(jù),f*的值與的值與n比較接近比較接近.當(dāng)當(dāng)m不不太大也不太小時(shí)太大也不太小時(shí),f*的值較大的值較大.(我出隨機(jī)數(shù)據(jù)的方法是我出隨機(jī)數(shù)據(jù)的方法是:固定地為源點(diǎn)和固定地為源點(diǎn)和匯點(diǎn)連上一些邊匯點(diǎn)連上一

12、些邊,然后隨機(jī)生成中間的邊然后隨機(jī)生成中間的邊.中間的邊保證邊的兩個(gè)端點(diǎn)的編號(hào)相差中間的邊保證邊的兩個(gè)端點(diǎn)的編號(hào)相差不太大不太大.這與不少題目轉(zhuǎn)成網(wǎng)絡(luò)流后形成這與不少題目轉(zhuǎn)成網(wǎng)絡(luò)流后形成的圖相似的圖相似)f f* *的理論上界的理論上界考慮每一次增廣考慮每一次增廣,至少有一條邊的至少有一條邊的r(u,v)值等于增廣路徑的流量值等于增廣路徑的流量.稱這些邊為臨界稱這些邊為臨界邊邊.增廣之后增廣之后,這條臨界邊就在殘量網(wǎng)絡(luò)中這條臨界邊就在殘量網(wǎng)絡(luò)中消失消失.假設(shè)一條臨界邊對(duì)應(yīng)一次增廣假設(shè)一條臨界邊對(duì)應(yīng)一次增廣(事實(shí)上很事實(shí)上很難達(dá)到這樣難達(dá)到這樣),令每條邊成為臨界邊的次數(shù)令每條邊成為臨界邊的次數(shù)

13、為為k(u,v),則有則有f* = O(m*k).k的上界的上界?k k的上界的上界如果要讓一條曾經(jīng)的臨界邊如果要讓一條曾經(jīng)的臨界邊(u,v)再次成為臨界邊再次成為臨界邊,則必須有一條增廣路徑包含邊則必須有一條增廣路徑包含邊(v,u).因?yàn)槊看卧鰪V因?yàn)槊看卧鰪V之后臨界邊就消失之后臨界邊就消失,要讓他再次成為臨界邊至少要要讓他再次成為臨界邊至少要讓他再次在殘量網(wǎng)絡(luò)中出現(xiàn)讓他再次在殘量網(wǎng)絡(luò)中出現(xiàn),即即(v,u)要被增廣要被增廣.結(jié)合上面的結(jié)論可以證明結(jié)合上面的結(jié)論可以證明,當(dāng)算法取的增廣路總是當(dāng)算法取的增廣路總是殘量網(wǎng)絡(luò)中的最短路殘量網(wǎng)絡(luò)中的最短路,任意一條邊成為臨界邊的次任意一條邊成為臨界邊的次

14、數(shù)至多為數(shù)至多為n/2-1.因此因此,增廣路算法的效率為增廣路算法的效率為O(f*m) = O(km2) = O(nm2). (這只是個(gè)上界這只是個(gè)上界,一般情況是達(dá)不到的一般情況是達(dá)不到的)備注中為增廣路算法我的代碼實(shí)現(xiàn)。數(shù)組備注中為增廣路算法我的代碼實(shí)現(xiàn)。數(shù)組u是殘量是殘量網(wǎng)絡(luò)的容量。網(wǎng)絡(luò)的容量。預(yù)流推進(jìn)算法預(yù)流推進(jìn)算法下面將介紹一個(gè)更直觀且時(shí)間效率下面將介紹一個(gè)更直觀且時(shí)間效率更優(yōu)的算法更優(yōu)的算法.一個(gè)直觀的想法一個(gè)直觀的想法如果給你一個(gè)網(wǎng)絡(luò)流如果給你一個(gè)網(wǎng)絡(luò)流,讓你手算出它的最讓你手算出它的最大流大流,你會(huì)怎么算你會(huì)怎么算?一般人都會(huì)嘗試著從源點(diǎn)出發(fā)一般人都會(huì)嘗試著從源點(diǎn)出發(fā),讓每條邊

15、讓每條邊的流量盡可能得大的流量盡可能得大,然后一點(diǎn)點(diǎn)往匯點(diǎn)推然后一點(diǎn)點(diǎn)往匯點(diǎn)推,直到遇到一條比較窄的弧直到遇到一條比較窄的弧,原先的流量過(guò)原先的流量過(guò)不去了不去了,這才減少原先的流量這才減少原先的流量.v1tsv2(0,2)(4,4)(0,4)(3,3)(0,2)例例2.一個(gè)直觀的想法一個(gè)直觀的想法大致的思路：從源點(diǎn)出發(fā)，大致的思路：從源點(diǎn)出發(fā)，逐步推進(jìn)。逐步推進(jìn)。稱當(dāng)前狀態(tài)下不滿足流量稱當(dāng)前狀態(tài)下不滿足流量平衡的結(jié)點(diǎn)為平衡的結(jié)點(diǎn)為“溢出的結(jié)溢出的結(jié)點(diǎn)點(diǎn)”.(對(duì)于結(jié)點(diǎn)對(duì)于結(jié)點(diǎn)u,f(V,u) 0 )令令e(u) = f(V,u),稱為稱為u點(diǎn)的點(diǎn)的贏余，直觀地描述，就是贏余，直觀地描述，就是“

16、流入的比流出的多多流入的比流出的多多少少”。e(v1)=4,e(v2)=3。不斷將溢出的結(jié)點(diǎn)中的贏不斷將溢出的結(jié)點(diǎn)中的贏余往后繼點(diǎn)推進(jìn)余往后繼點(diǎn)推進(jìn),直到贏余直到贏余都聚集在都聚集在t.v1tsv2(2,2)(4,4)(0,4)(3,3)(2,2)如果多推了一些流量如果多推了一些流量, 我們可以再把它推回我們可以再把它推回來(lái)來(lái). (如如e(v2)=3,但這但這3個(gè)單位的贏余已經(jīng)沒(méi)個(gè)單位的贏余已經(jīng)沒(méi)地方去了地方去了,只能推回只能推回來(lái)來(lái).)(沿著后向弧沿著后向弧)這副這副圖是原網(wǎng)絡(luò)而不是殘圖是原網(wǎng)絡(luò)而不是殘量網(wǎng)絡(luò)量網(wǎng)絡(luò),因此沒(méi)把后項(xiàng)因此沒(méi)把后項(xiàng)弧畫出來(lái)弧畫出來(lái))例例2.2.一個(gè)直觀的想法一個(gè)直觀

17、的想法v1tsv2(2,2)(4,4)(0,4)(3,3)(2,2)程序沒(méi)有全局觀程序沒(méi)有全局觀?!?!此時(shí)此時(shí)e(v2)=3.正確的回正確的回推法是往推法是往(v2,s)推推1,往往(v2,v1)推推2,然后使得這然后使得這2個(gè)單位的贏余可以從個(gè)單位的贏余可以從(v1,t)推到推到t上。上。但程序沒(méi)有全局觀但程序沒(méi)有全局觀,它它萬(wàn)一往萬(wàn)一往(v2,s)推了推了3個(gè)單個(gè)單位怎么辦位怎么辦?我們總不能我們總不能嘗試所有的可能性吧嘗試所有的可能性吧,那樣就變成搜索了那樣就變成搜索了.引導(dǎo)機(jī)制引導(dǎo)機(jī)制把流推錯(cuò)可能導(dǎo)致產(chǎn)生的流不是最大流把流推錯(cuò)可能導(dǎo)致產(chǎn)生的流不是最大流.我們需要有一個(gè)能引導(dǎo)流的推進(jìn)方

18、向的我們需要有一個(gè)能引導(dǎo)流的推進(jìn)方向的機(jī)制機(jī)制,當(dāng)它發(fā)現(xiàn)我們先前的推進(jìn)是錯(cuò)誤的當(dāng)它發(fā)現(xiàn)我們先前的推進(jìn)是錯(cuò)誤的時(shí)候時(shí)候,能沿著正確的后向弧回推回來(lái)能沿著正確的后向弧回推回來(lái).由于建立了后向弧由于建立了后向弧,正推與回推在程序中正推與回推在程序中并無(wú)卻別，都是在推殘量網(wǎng)絡(luò)中的一條并無(wú)卻別，都是在推殘量網(wǎng)絡(luò)中的一條邊邊.高度標(biāo)號(hào)的引導(dǎo)作用高度標(biāo)號(hào)的引導(dǎo)作用高度標(biāo)號(hào)就是這樣的一個(gè)引導(dǎo)機(jī)制高度標(biāo)號(hào)就是這樣的一個(gè)引導(dǎo)機(jī)制.我們規(guī)定我們規(guī)定,如果一個(gè)結(jié)點(diǎn)溢出了如果一個(gè)結(jié)點(diǎn)溢出了,那么他的那么他的多余的流量只能流向高度標(biāo)號(hào)比自己低多余的流量只能流向高度標(biāo)號(hào)比自己低的結(jié)點(diǎn)的結(jié)點(diǎn).(“水往低處流水往低處流”)當(dāng)然

19、當(dāng)然,高度標(biāo)號(hào)不可能事先知道往哪些方高度標(biāo)號(hào)不可能事先知道往哪些方向推才是正確的向推才是正確的.它將按情況動(dòng)態(tài)改變自它將按情況動(dòng)態(tài)改變自己的值己的值,從而正確地引導(dǎo)流向從而正確地引導(dǎo)流向.重標(biāo)號(hào)操作重標(biāo)號(hào)操作當(dāng)一個(gè)結(jié)點(diǎn)有贏余當(dāng)一個(gè)結(jié)點(diǎn)有贏余(溢出了溢出了), 周圍卻沒(méi)有周圍卻沒(méi)有高度比它低的結(jié)點(diǎn)時(shí)候高度比它低的結(jié)點(diǎn)時(shí)候,我們就用重標(biāo)號(hào)我們就用重標(biāo)號(hào)操作使它的標(biāo)號(hào)上升到比周圍最低的結(jié)操作使它的標(biāo)號(hào)上升到比周圍最低的結(jié)點(diǎn)略高一點(diǎn)點(diǎn)略高一點(diǎn),使他的贏余能流出去使他的贏余能流出去.贏余千萬(wàn)不能困在某個(gè)結(jié)點(diǎn)里贏余千萬(wàn)不能困在某個(gè)結(jié)點(diǎn)里.對(duì)于任意對(duì)于任意一個(gè)非源非匯的結(jié)點(diǎn)，有贏余就意味著一個(gè)非源非匯的結(jié)點(diǎn)

20、，有贏余就意味著它不滿足流量平衡，也就意味著整個(gè)網(wǎng)它不滿足流量平衡，也就意味著整個(gè)網(wǎng)絡(luò)流不是一個(gè)真正合法的網(wǎng)絡(luò)流。絡(luò)流不是一個(gè)真正合法的網(wǎng)絡(luò)流。重標(biāo)號(hào)操作重標(biāo)號(hào)操作對(duì)于例對(duì)于例2的這種情況的這種情況,v2中過(guò)多的贏余最中過(guò)多的贏余最終會(huì)沿著終會(huì)沿著(v2,v1)、(v2,s)流回去流回去(雖然他雖然他們一開始流錯(cuò)了方向們一開始流錯(cuò)了方向,但后來(lái)又被回推但后來(lái)又被回推,等等于說(shuō)是被改正了于說(shuō)是被改正了)。只有當(dāng)非源非匯的結(jié)點(diǎn)中的贏余全部流只有當(dāng)非源非匯的結(jié)點(diǎn)中的贏余全部流到匯點(diǎn)或流回源點(diǎn)后，這個(gè)流才重新合到匯點(diǎn)或流回源點(diǎn)后，這個(gè)流才重新合法。法。高度函數(shù)高度函數(shù)高度函數(shù)高度函數(shù)h(v)返回一個(gè)返

21、回一個(gè)v的高度標(biāo)號(hào)。的高度標(biāo)號(hào)。高度函數(shù)有三個(gè)基本條件：高度函數(shù)有三個(gè)基本條件：h(s) = |V|h(t) = 0對(duì)于對(duì)于Ef(殘量網(wǎng)絡(luò)殘量網(wǎng)絡(luò))中的每一條邊中的每一條邊(u,v),(r(u,v)0)h(u) 0,那就表示那就表示從從u到到v還可以增加流量還可以增加流量,那那h(u)就應(yīng)該比就應(yīng)該比h(v)高才對(duì)高才對(duì).的的確確,我們后面還將規(guī)定我們后面還將規(guī)定,只有在只有在h(u)h(v)的時(shí)候才能應(yīng)的時(shí)候才能應(yīng)用推進(jìn)操作用推進(jìn)操作(將一個(gè)結(jié)點(diǎn)的盈余推進(jìn)到另一個(gè)結(jié)點(diǎn)的操將一個(gè)結(jié)點(diǎn)的盈余推進(jìn)到另一個(gè)結(jié)點(diǎn)的操作作).而高度函數(shù)為了滿足其合法性而高度函數(shù)為了滿足其合法性,還要滿足上述的這還要滿足

22、上述的這三個(gè)條件三個(gè)條件.后面我們將利用這三個(gè)條件證明預(yù)流推進(jìn)算后面我們將利用這三個(gè)條件證明預(yù)流推進(jìn)算法的正確性。法的正確性。高度函數(shù)的條件的實(shí)質(zhì)高度函數(shù)的條件的實(shí)質(zhì)h(u) 0，r(u,v)0, h(u) = h(v)+1（u溢出，溢出，(u,v)在殘量網(wǎng)絡(luò)中，兩者的高在殘量網(wǎng)絡(luò)中，兩者的高度差為度差為1）推進(jìn)量為推進(jìn)量為e(u)與與r(u,v)的最小值。的最小值。推進(jìn)時(shí)同時(shí)更改相關(guān)的推進(jìn)時(shí)同時(shí)更改相關(guān)的r與與e的值。的值。推進(jìn)操作推進(jìn)操作 偽代碼偽代碼Procedure Push(u,v)lX min e(u), r(u,v) lDec(r(u,v), x)Inc(r(v,u), x)lD

23、ec(e(u), x) Inc(e(v), x)重標(biāo)號(hào)操作重標(biāo)號(hào)操作使用對(duì)象：使用對(duì)象： 一個(gè)結(jié)點(diǎn)一個(gè)結(jié)點(diǎn)u使用條件：使用條件：結(jié)點(diǎn)結(jié)點(diǎn)u溢出；殘量網(wǎng)絡(luò)中周圍所有的點(diǎn)的溢出；殘量網(wǎng)絡(luò)中周圍所有的點(diǎn)的高度都不比它低。高度都不比它低。Relabel(u)lu(u) = min h(v) | (u,v)是殘量網(wǎng)絡(luò)總的邊是殘量網(wǎng)絡(luò)總的邊 + 1使用了重標(biāo)號(hào)操作后使用了重標(biāo)號(hào)操作后,至少存在一個(gè)至少存在一個(gè)(u,v)滿足滿足h(u)=h(v)+1.預(yù)流初始化預(yù)流初始化(Init-Preflow(Init-Preflow) )一開始的時(shí)候，我們要讓和源點(diǎn)一開始的時(shí)候，我們要讓和源點(diǎn)s相關(guān)連的邊相關(guān)連的邊都

24、盡可能的充滿。但由于都盡可能的充滿。但由于s沒(méi)有溢出，不符合沒(méi)有溢出，不符合推進(jìn)操作的使用條件，我們需要另寫一段初始推進(jìn)操作的使用條件，我們需要另寫一段初始化的代碼。還得做的一件事是初始化高度函數(shù)化的代碼。還得做的一件事是初始化高度函數(shù).h(s) = n h(v) = 0 (vs)對(duì)于所有與對(duì)于所有與s相關(guān)聯(lián)的點(diǎn)相關(guān)聯(lián)的點(diǎn)v，lInc( e(v), c(s,v) ), Dec( e(s), c(s,v) )l將邊將邊(s,v)反向，變成反向，變成(v,s) （在殘量網(wǎng)絡(luò)中）。（在殘量網(wǎng)絡(luò)中）。初始化過(guò)后，初始化過(guò)后，e(s)變成負(fù)數(shù)。變成負(fù)數(shù)。結(jié)論結(jié)論5 5對(duì)于一個(gè)對(duì)于一個(gè)溢出的結(jié)點(diǎn)溢出的結(jié)點(diǎn)

25、，兩個(gè)關(guān)鍵操作（推進(jìn)，兩個(gè)關(guān)鍵操作（推進(jìn)和重標(biāo)號(hào)）能且只能應(yīng)用一個(gè)。和重標(biāo)號(hào)）能且只能應(yīng)用一個(gè)。證明：對(duì)于一個(gè)溢出的結(jié)點(diǎn)證明：對(duì)于一個(gè)溢出的結(jié)點(diǎn)u,和所有與他相和所有與他相關(guān)聯(lián)的點(diǎn)關(guān)聯(lián)的點(diǎn)v( (u,v)在殘量網(wǎng)絡(luò)中存在在殘量網(wǎng)絡(luò)中存在),必然有必然有h(u) = h(v) + 1.(由高度函數(shù)的定義由高度函數(shù)的定義).根據(jù)根據(jù)v分成兩種情況分成兩種情況:1).所有所有v都有都有h(u)h(v)+1 2).至少存在一個(gè)至少存在一個(gè)v,使得使得h(u)=h(v)+1. 而而1)2)互為否命題互為否命題,不能同時(shí)成不能同時(shí)成立或同時(shí)不成立立或同時(shí)不成立.那么那么1)對(duì)應(yīng)重標(biāo)號(hào)對(duì)應(yīng)重標(biāo)號(hào),2)對(duì)應(yīng)推

26、對(duì)應(yīng)推進(jìn)進(jìn),兩者必能應(yīng)用一個(gè)且只能應(yīng)用一個(gè)兩者必能應(yīng)用一個(gè)且只能應(yīng)用一個(gè).一般的預(yù)流推進(jìn)算法一般的預(yù)流推進(jìn)算法由輔助定理由輔助定理5,得到了一個(gè)一般的預(yù)流推得到了一個(gè)一般的預(yù)流推進(jìn)算法進(jìn)算法.(好短好短)Init-PreflowWhile 存在一個(gè)溢出的結(jié)點(diǎn)存在一個(gè)溢出的結(jié)點(diǎn)l選一個(gè)結(jié)點(diǎn)選一個(gè)結(jié)點(diǎn),應(yīng)用相應(yīng)的關(guān)鍵操作應(yīng)用相應(yīng)的關(guān)鍵操作(推進(jìn)或重推進(jìn)或重標(biāo)號(hào)標(biāo)號(hào)).當(dāng)不存在溢出結(jié)點(diǎn)時(shí)當(dāng)不存在溢出結(jié)點(diǎn)時(shí)(s,t不算不算),算法結(jié)束算法結(jié)束,得到一個(gè)可行流得到一個(gè)可行流,并且還是最大流并且還是最大流.預(yù)流推進(jìn)算法的正確性預(yù)流推進(jìn)算法的正確性預(yù)流只是不滿足流量平衡預(yù)流只是不滿足流量平衡,網(wǎng)絡(luò)流的前兩網(wǎng)

27、絡(luò)流的前兩條性質(zhì)條性質(zhì)-容量限制和反對(duì)稱性它還是滿容量限制和反對(duì)稱性它還是滿足的足的.當(dāng)不存在溢出結(jié)點(diǎn)時(shí)當(dāng)不存在溢出結(jié)點(diǎn)時(shí),流量平衡也滿流量平衡也滿足了足了.所以所以,當(dāng)算法結(jié)束時(shí)當(dāng)算法結(jié)束時(shí),我們得到一個(gè)可行流我們得到一個(gè)可行流(合法流合法流).為什么他是一個(gè)最大流呢為什么他是一個(gè)最大流呢?下面先看幾個(gè)結(jié)論下面先看幾個(gè)結(jié)論:結(jié)論結(jié)論6(6(結(jié)點(diǎn)高度永不下降結(jié)點(diǎn)高度永不下降) )只有重標(biāo)號(hào)操作能更改結(jié)點(diǎn)的高度標(biāo)號(hào)只有重標(biāo)號(hào)操作能更改結(jié)點(diǎn)的高度標(biāo)號(hào).在重標(biāo)號(hào)操作應(yīng)用前在重標(biāo)號(hào)操作應(yīng)用前,必有必有h(u) = h(u) + 1.所以所以,在重標(biāo)號(hào)操作后在重標(biāo)號(hào)操作后,高度標(biāo)號(hào)至少高度標(biāo)號(hào)至少+1.

28、結(jié)論結(jié)論7 7在算法執(zhí)行過(guò)程中在算法執(zhí)行過(guò)程中,h始終是一個(gè)合法的始終是一個(gè)合法的高度函數(shù)高度函數(shù).(滿足那三個(gè)條件滿足那三個(gè)條件)1).考察一個(gè)被重標(biāo)號(hào)的結(jié)點(diǎn)考察一個(gè)被重標(biāo)號(hào)的結(jié)點(diǎn)u.l設(shè)設(shè)(u,v)存在于存在于Ef,v0是所有是所有v中中h最小的一個(gè)最小的一個(gè). H(u)=h(v0)+1,滿足滿足h(u)=h(v0)+1,而而h(v0) = h(v),所以所以 h(u)=h(v)+1.l設(shè)設(shè)(w,u)存在于存在于Ef,則則h(w)=h(u)+1=h(u)+1.仍舊滿足仍舊滿足.結(jié)論結(jié)論7 7在算法執(zhí)行過(guò)程中在算法執(zhí)行過(guò)程中,h始終是一個(gè)合法的始終是一個(gè)合法的高度函數(shù)高度函數(shù).(滿足那三個(gè)條

29、件滿足那三個(gè)條件)2).考察一個(gè)被推進(jìn)的邊考察一個(gè)被推進(jìn)的邊(u,v).l(v,u)可能是在這次推進(jìn)之后才出現(xiàn)在可能是在這次推進(jìn)之后才出現(xiàn)在Ef中中.它的出現(xiàn)使得新增了一個(gè)限制條它的出現(xiàn)使得新增了一個(gè)限制條件件:h(v)=h(u)+1.不過(guò)不過(guò),這顯然是滿足的這顯然是滿足的,因因?yàn)橥七M(jìn)操作的使用條件是為推進(jìn)操作的使用條件是h(u)=h(v)+1.那么那么h(v)=h(u)-1 = h(u)+1結(jié)論結(jié)論8(8(預(yù)流中無(wú)增廣路預(yù)流中無(wú)增廣路) )當(dāng)當(dāng)h是一個(gè)合法的高度函數(shù)時(shí)是一個(gè)合法的高度函數(shù)時(shí),Gf中始終中始終不存在增廣路不存在增廣路.(這個(gè)定理展示了這個(gè)定理展示了h的條件的條件的重要性和巧妙性

30、的重要性和巧妙性)證明證明:假設(shè)存在增廣路假設(shè)存在增廣路p=(v0,v1,vk),其其中中v0=s,vk=t.因?yàn)樵鰪V路徑中無(wú)重復(fù)因?yàn)樵鰪V路徑中無(wú)重復(fù)點(diǎn)點(diǎn),k+1=|V|,即即k|V|.結(jié)論結(jié)論8(8(預(yù)流中無(wú)增廣路預(yù)流中無(wú)增廣路) )fkkffEvvEvvEvv),(),(),(121101)()(1)()(1)()(12110kkvhvhvhvhvhvh相加得相加得:h(s)=h(t)+k=0+k=k而而k|V|,所以所以h(s)|V|.而根據(jù)定而根據(jù)定義義,h(s)=|V|.矛盾矛盾.預(yù)流推進(jìn)算法的正確性預(yù)流推進(jìn)算法的正確性當(dāng)有溢出結(jié)點(diǎn)時(shí)當(dāng)有溢出結(jié)點(diǎn)時(shí),根據(jù)結(jié)論根據(jù)結(jié)論5,必定可以在它上

31、面必定可以在它上面施加一個(gè)操作施加一個(gè)操作.當(dāng)算法停止時(shí)當(dāng)算法停止時(shí),因?yàn)闊o(wú)溢出結(jié)點(diǎn)因?yàn)闊o(wú)溢出結(jié)點(diǎn),所以當(dāng)前流是所以當(dāng)前流是一個(gè)合法流一個(gè)合法流,而根據(jù)結(jié)論而根據(jù)結(jié)論8,Gf中始終不存在增廣中始終不存在增廣路路.根據(jù)最大流最小割定理根據(jù)最大流最小割定理,當(dāng)當(dāng)Gf中不存在增廣中不存在增廣路時(shí)路時(shí),當(dāng)前流是最大流當(dāng)前流是最大流.(算法執(zhí)行了一半時(shí)雖然也沒(méi)有增廣路算法執(zhí)行了一半時(shí)雖然也沒(méi)有增廣路,但由于但由于它不是一個(gè)合法流它不是一個(gè)合法流,前面的諸多定理都不成立前面的諸多定理都不成立).算法的最優(yōu)性的保證者算法的最優(yōu)性的保證者:對(duì)于所有在對(duì)于所有在Ef中的中的(v,u), 均有均有h(v)0lh(

32、u) = h(v)+1可行邊集可行邊集Ef,h:所有由可行弧組成的集合。所有由可行弧組成的集合。可行網(wǎng)絡(luò)可行網(wǎng)絡(luò)Gf,h = (V,Ef,h)結(jié)論結(jié)論9,109,10結(jié)論結(jié)論9:可行網(wǎng)絡(luò)中無(wú)環(huán)可行網(wǎng)絡(luò)中無(wú)環(huán).(和結(jié)論和結(jié)論8的證明的證明類似類似,弄一堆式子然后疊加一下弄一堆式子然后疊加一下,導(dǎo)出矛盾導(dǎo)出矛盾)結(jié)論結(jié)論10:推進(jìn)操作永遠(yuǎn)不會(huì)新增可行弧推進(jìn)操作永遠(yuǎn)不會(huì)新增可行弧,卻卻可能使原有的可行弧消失可能使原有的可行弧消失.(根據(jù)可行弧的根據(jù)可行弧的定義顯然定義顯然)結(jié)論結(jié)論1111在在u被重標(biāo)號(hào)之后被重標(biāo)號(hào)之后:l1).至少有一條可行弧離開至少有一條可行弧離開u. 顯然顯然.設(shè)設(shè)v0是是u的

33、鄰居中的鄰居中h值最小的那一個(gè)值最小的那一個(gè),則則(u,v0)必定是一條可行弧必定是一條可行弧.l2).不可能有可行弧進(jìn)入不可能有可行弧進(jìn)入u. 假設(shè)有一條假設(shè)有一條(w,u).則則h(w) = h(u) + 1.根據(jù)輔根據(jù)輔助定理助定理6,relabel操作至少將結(jié)點(diǎn)的操作至少將結(jié)點(diǎn)的h+1,所以所以h(w) h(u) + 1.根據(jù)高度函數(shù)必須滿足的條根據(jù)高度函數(shù)必須滿足的條件件,(w,u)在在relabel前不在前不在Ef中中.而而relabel操作操作只改變可行網(wǎng)絡(luò)不改變殘量網(wǎng)絡(luò)只改變可行網(wǎng)絡(luò)不改變殘量網(wǎng)絡(luò),(w,u)不可不可能在能在relabel前存在于前存在于Ef而之后就不存在而之后

34、就不存在.當(dāng)前弧當(dāng)前弧每個(gè)結(jié)點(diǎn)有一個(gè)鄰居列表和有一個(gè)每個(gè)結(jié)點(diǎn)有一個(gè)鄰居列表和有一個(gè)“當(dāng)前弧當(dāng)前弧”的指針的指針,保存當(dāng)前檢查到鄰居列表中的哪一條保存當(dāng)前檢查到鄰居列表中的哪一條弧了。初始化時(shí)弧了。初始化時(shí),“當(dāng)前弧當(dāng)前弧”指向與該結(jié)點(diǎn)相連指向與該結(jié)點(diǎn)相連的第一條邊的第一條邊.鄰居列表保存的是所有可能成為鄰居列表保存的是所有可能成為可行弧的弧可行弧的弧.當(dāng)再次調(diào)用檢查操作時(shí)當(dāng)再次調(diào)用檢查操作時(shí),可以從上一次檢查了可以從上一次檢查了一半的地方繼續(xù)檢查一半的地方繼續(xù)檢查.具體請(qǐng)看下面檢查操作的偽代碼具體請(qǐng)看下面檢查操作的偽代碼:檢查操作檢查操作Check(u)lWhile e(u)0 dolIf c

35、urrent(u)degree(u) then /當(dāng)沒(méi)有可行弧可當(dāng)沒(méi)有可行弧可以推進(jìn)以推進(jìn),該結(jié)點(diǎn)卻仍舊有贏余時(shí)該結(jié)點(diǎn)卻仍舊有贏余時(shí),重標(biāo)號(hào)重標(biāo)號(hào).lRelabel(u)lCurrent(u) = 1lElselIf (u,current(u) 是一條可行弧是一條可行弧 then Push(u,current(u) /push了之后就不能增加了之后就不能增加 current(u)的值的值.因?yàn)檫@如果是一次非飽和推進(jìn)因?yàn)檫@如果是一次非飽和推進(jìn),那再下那再下一次檢查時(shí)還是可以沿著這條弧做推進(jìn)一次檢查時(shí)還是可以沿著這條弧做推進(jìn).lElse Inc(current(u)當(dāng)前弧的正確性當(dāng)前弧的正確性Cu

36、rrent是全局變量是全局變量,當(dāng)某次當(dāng)某次Check操作操作結(jié)束時(shí)他的值并沒(méi)有被清空結(jié)束時(shí)他的值并沒(méi)有被清空.比如結(jié)點(diǎn)比如結(jié)點(diǎn)u有有10個(gè)鄰居個(gè)鄰居,上次檢查到第上次檢查到第7個(gè)個(gè),那再一次那再一次Check(u)的時(shí)候就只要從第的時(shí)候就只要從第7個(gè)開始檢查就可以了。個(gè)開始檢查就可以了。為什么再一次檢查的時(shí)候不要檢查第為什么再一次檢查的時(shí)候不要檢查第1-6條邊了條邊了?能否證明在再一次檢查的時(shí)候他能否證明在再一次檢查的時(shí)候他們一定不是可行弧們一定不是可行弧?當(dāng)前弧的正確性當(dāng)前弧的正確性在在relabel-to-front算法中算法中,relabel只被只被Check調(diào)用調(diào)用.當(dāng)當(dāng)“當(dāng)前弧當(dāng)前

37、弧”移動(dòng)時(shí)移動(dòng)時(shí),移動(dòng)前它指向的那移動(dòng)前它指向的那條弧一定是不可行的條弧一定是不可行的.而推進(jìn)操作不能創(chuàng)而推進(jìn)操作不能創(chuàng)造可行弧造可行弧.只有只有relabel可以可以.兩次兩次Check之間沒(méi)有之間沒(méi)有relabel操作操作.所以原先的不可行所以原先的不可行的弧在第二次的弧在第二次Check之前一直是不可行之前一直是不可行的的.RelabelRelabel-to-front-to-frontInit-Preflow初始化結(jié)點(diǎn)初始化結(jié)點(diǎn)(除除s,t)列表列表L(任何順序均可任何順序均可)令所有令所有u,Current(u) = 1u HeadLWhile u nil dolOld-height

38、 h(u)lCheck(u)lIf h(u) old-height then 將將u移到移到L首部首部l/如果如果h(u)比原先的比原先的h高了高了,說(shuō)明說(shuō)明被被relabel,移到隊(duì)首移到隊(duì)首.lu next(u)圖例圖例 ( (初始狀態(tài)初始狀態(tài). .結(jié)點(diǎn)下方數(shù)字為贏余結(jié)點(diǎn)下方數(shù)字為贏余,N,N顯示的顯示的是鄰居列表是鄰居列表,N,N中紅色的是當(dāng)前弧指針?biāo)诘奈恢屑t色的是當(dāng)前弧指針?biāo)诘奈恢弥?) .)S-26x12y14z0t06543210(12/12)(14/14)(0/16)(0/7)(0,5)(0,8)(0,10)L x y zN s s xy x yz z tt圖例圖例:x:x被

39、檢查并重標(biāo)號(hào)被檢查并重標(biāo)號(hào), ,并被提到并被提到L L的首部的首部( (等于等于沒(méi)提沒(méi)提). ).注意當(dāng)前弧的指針移到了注意當(dāng)前弧的指針移到了t. xt. x的所有贏余的所有贏余推給了推給了y y和和t. t.S-26x0y19z0t76543210(12/12)(14/14)(7/16)(0/7)(5,5)(0,8)(0,10)L x y zN s s xy x yz z tt圖例圖例 :y:y正在被檢查正在被檢查. .將將8 8單位的贏余推給單位的贏余推給z z之后還之后還是有剩余是有剩余. .S-26x0y11z8t76543210(12/12)(14/14)(7/16)(0/7)(5,

40、5)(8,8)(0,10)L x y zN s s xy x yz z tt圖例圖例 : :一次必須把贏余全部推光一次必須把贏余全部推光. .所以所以y y被重標(biāo)號(hào)被重標(biāo)號(hào), ,當(dāng)前弧當(dāng)前弧指針從頭開始查找指針從頭開始查找, ,找到找到(y,x)(y,x)這條可行弧之后進(jìn)行推進(jìn)這條可行弧之后進(jìn)行推進(jìn). .實(shí)際上是把多推的贏余還給了實(shí)際上是把多推的贏余還給了x.x.因?yàn)橐驗(yàn)閔(u)=h(v)+1h(u)=h(v)+1的的保證保證, ,它沒(méi)有把贏余錯(cuò)推給它沒(méi)有把贏余錯(cuò)推給s.s.S-26x5y6z8t76543210(12/12)(14/14)(7/16)(0/7)(0,5)(8,8)(0,10)

41、L x y zN s s xy x yz z tt圖例圖例:y:y還是有贏余還是有贏余. .當(dāng)當(dāng)前弧移動(dòng)到另局列表的尾部時(shí)當(dāng)當(dāng)前弧移動(dòng)到另局列表的尾部時(shí),y,y再一次被重標(biāo)號(hào)再一次被重標(biāo)號(hào), ,并把贏余還給并把贏余還給s.s.檢查結(jié)束檢查結(jié)束,y,y被提到被提到L L列表列表的首部的首部. .S-20 x5y0z8t76543210(12/12)(8/14)(7/16)(0/7)(0,5)(8,8)(0,10)L y x zN s s xx y yz z tt圖例圖例: :檢查檢查x.x.注意注意x x的當(dāng)前弧指針已經(jīng)指在的當(dāng)前弧指針已經(jīng)指在t t上了上了. . x x把贏余推給把贏余推給t.

42、 ut. u指針直接后移指針直接后移.( .(因?yàn)橐驗(yàn)閤 x沒(méi)有被重沒(méi)有被重標(biāo)號(hào)標(biāo)號(hào)) )S-20 x0y0z8t126543210(12/12)(8/14)(12/16)(0/7)(0,5)(8,8)(0,10)L y x zN s s xx y yz z tt圖例圖例:z:z被檢查并被提到列表首部被檢查并被提到列表首部. .S-20 x0y0z0t206543210(12/12)(8/14)(12/16)(0/7)(0,5)(8,8)(8,10)L z y xN x s sy x ytz zt圖例圖例:u:u指針從指針從y y開始向后移動(dòng)開始向后移動(dòng), ,直到隊(duì)尾也沒(méi)有發(fā)直到隊(duì)尾也沒(méi)有發(fā)現(xiàn)

43、可以檢查的結(jié)點(diǎn)現(xiàn)可以檢查的結(jié)點(diǎn)( (只有溢出的結(jié)點(diǎn)才能被檢查只有溢出的結(jié)點(diǎn)才能被檢查). ).算法結(jié)束算法結(jié)束. .S-20 x0y0z0t206543210(12/12)(8/14)(12/16)(0/7)(0,5)(8,8)(8,10)L z y xN x s sy x ytz ztrelabelrelabel-to-front-to-front的正確性的正確性前面我們已經(jīng)證明了一般預(yù)流推進(jìn)算法前面我們已經(jīng)證明了一般預(yù)流推進(jìn)算法的正確性了的正確性了.因此因此,現(xiàn)在只要證明現(xiàn)在只要證明,在在relabel-to-front算法結(jié)束時(shí)算法結(jié)束時(shí),一般預(yù)流推一般預(yù)流推進(jìn)算法的結(jié)束條件也正好被滿足

44、進(jìn)算法的結(jié)束條件也正好被滿足-即沒(méi)即沒(méi)有溢出的結(jié)點(diǎn)有溢出的結(jié)點(diǎn).結(jié)論結(jié)論11:L11:L始終拓?fù)溆行蚴冀K拓?fù)溆行驅(qū)τ趯?duì)于G上的可行網(wǎng)絡(luò)上的可行網(wǎng)絡(luò)Gf,h,列表列表L中的結(jié)點(diǎn)中的結(jié)點(diǎn)始終保持拓?fù)溆行蛐允冀K保持拓?fù)溆行蛐?一開始的時(shí)候一開始的時(shí)候,列表中所有結(jié)點(diǎn)列表中所有結(jié)點(diǎn)(s,t不在不在列表中列表中)的高度均為的高度均為0,不存在高度差不存在高度差,所以所以不存在可行弧不存在可行弧.這時(shí)列表顯然拓?fù)溆行蜻@時(shí)列表顯然拓?fù)溆行?一個(gè)結(jié)點(diǎn)被一個(gè)結(jié)點(diǎn)被relabel之后之后,就被提到列表的就被提到列表的首部首部.根據(jù)輔助定理根據(jù)輔助定理11,relabel之后沒(méi)有之后沒(méi)有可行弧進(jìn)入結(jié)點(diǎn)可行弧進(jìn)入結(jié)點(diǎn)

45、,但有可行弧離開結(jié)點(diǎn)但有可行弧離開結(jié)點(diǎn),所所以將結(jié)點(diǎn)提到列表首部仍舊使列表滿足以將結(jié)點(diǎn)提到列表首部仍舊使列表滿足拓?fù)溆行蛲負(fù)溆行?推進(jìn)操作不能創(chuàng)造可行弧推進(jìn)操作不能創(chuàng)造可行弧,因此與列表的因此與列表的拓?fù)溆行蛐詿o(wú)關(guān)拓?fù)溆行蛐詿o(wú)關(guān).結(jié)論結(jié)論1212L中指針中指針u之前的結(jié)點(diǎn)全部是非溢出結(jié)點(diǎn)之前的結(jié)點(diǎn)全部是非溢出結(jié)點(diǎn).當(dāng)一個(gè)結(jié)點(diǎn)被檢查之后當(dāng)一個(gè)結(jié)點(diǎn)被檢查之后,它必定沒(méi)有贏余它必定沒(méi)有贏余,因此因此將將u指針后移不影響上面的性質(zhì)指針后移不影響上面的性質(zhì).它自己沒(méi)有贏余了它自己沒(méi)有贏余了,但它卻可能將贏余推給了但它卻可能將贏余推給了別人別人.如果推給在如果推給在L中位置在它后面的結(jié)點(diǎn)不要中位置在它后面

46、的結(jié)點(diǎn)不要緊緊.但如果它把贏余推給了在自己之前的結(jié)點(diǎn)但如果它把贏余推給了在自己之前的結(jié)點(diǎn)呢呢?因?yàn)橐驗(yàn)長(zhǎng)拓?fù)溆行蛲負(fù)溆行?他若把贏余推給了排在自己前他若把贏余推給了排在自己前面的結(jié)點(diǎn)面的結(jié)點(diǎn),則必定發(fā)生了則必定發(fā)生了relabel操作操作.而如果有而如果有relabel,則它已經(jīng)被提到列表的首部了則它已經(jīng)被提到列表的首部了.性質(zhì)依性質(zhì)依然滿足然滿足.這就是算法名這就是算法名:relabel-to-front的由來(lái)的由來(lái).RelabelRelabel-to-front-to-front根據(jù)一般的預(yù)流推進(jìn)算法根據(jù)一般的預(yù)流推進(jìn)算法,當(dāng)沒(méi)有溢出結(jié)當(dāng)沒(méi)有溢出結(jié)點(diǎn)時(shí)算法就結(jié)束并得到一個(gè)最大流點(diǎn)時(shí)算法就結(jié)

47、束并得到一個(gè)最大流.而而relabel-to-front算法的結(jié)束條件是算法的結(jié)束條件是u指指針指向針指向L隊(duì)列尾部隊(duì)列尾部.根據(jù)輔助定理根據(jù)輔助定理12,u以前的結(jié)點(diǎn)均非溢出以前的結(jié)點(diǎn)均非溢出結(jié)點(diǎn)結(jié)點(diǎn).所以當(dāng)所以當(dāng)u指向尾部時(shí)指向尾部時(shí),所有的結(jié)點(diǎn)均所有的結(jié)點(diǎn)均沒(méi)有溢出沒(méi)有溢出.另外可以證明另外可以證明,算法的復(fù)雜度為算法的復(fù)雜度為O(n3).Highest-relabelHighest-relabel還可以改進(jìn)還可以改進(jìn).經(jīng)驗(yàn)表明經(jīng)驗(yàn)表明,總是檢查高度標(biāo)號(hào)最大的結(jié)點(diǎn)，總是檢查高度標(biāo)號(hào)最大的結(jié)點(diǎn)，會(huì)有比較好的效率會(huì)有比較好的效率.于是對(duì)于是對(duì)Relabel-to-front進(jìn)行了一點(diǎn)小修進(jìn)行

48、了一點(diǎn)小修改改,得到了得到了highest-relabel算法算法.分塊的分塊的L L列表列表可以證明可以證明,任意結(jié)點(diǎn)的最大的距離標(biāo)號(hào)為任意結(jié)點(diǎn)的最大的距離標(biāo)號(hào)為2n-1.將將L列表分成列表分成2n個(gè)塊個(gè)塊,第第1塊保存所有高度塊保存所有高度為為0的點(diǎn)的點(diǎn),第第i+1塊保存高度為塊保存高度為I的所有結(jié)點(diǎn)的所有結(jié)點(diǎn).從最后一塊開始往前找從最后一塊開始往前找,發(fā)現(xiàn)一個(gè)不為空發(fā)現(xiàn)一個(gè)不為空的塊就把這個(gè)塊里的結(jié)點(diǎn)全部檢查掉的塊就把這個(gè)塊里的結(jié)點(diǎn)全部檢查掉.如如果有元素被重標(biāo)號(hào)了果有元素被重標(biāo)號(hào)了,那就將他移動(dòng)到新那就將他移動(dòng)到新的塊里的塊里,并從那個(gè)新的塊的前面開始繼續(xù)并從那個(gè)新的塊的前面開始繼續(xù)往

49、下查找往下查找.分塊的分塊的L L列表列表對(duì)于可行網(wǎng)絡(luò)對(duì)于可行網(wǎng)絡(luò),分塊分塊L列表是拓?fù)溆行虻牧斜硎峭負(fù)溆行虻?因?yàn)榭尚谢∫驗(yàn)榭尚谢?u,v)要求要求h(u) = h(v) + 1,即即只有從標(biāo)號(hào)高的結(jié)點(diǎn)指向標(biāo)號(hào)低的結(jié)點(diǎn)只有從標(biāo)號(hào)高的結(jié)點(diǎn)指向標(biāo)號(hào)低的結(jié)點(diǎn).既只有從后面的塊里的結(jié)點(diǎn)指向前面的既只有從后面的塊里的結(jié)點(diǎn)指向前面的塊里的結(jié)點(diǎn)塊里的結(jié)點(diǎn).所以所以,這種分塊方法仍然保持這種分塊方法仍然保持了整個(gè)列表的拓?fù)溆行蛐粤苏麄€(gè)列表的拓?fù)溆行蛐?因此因此,算法結(jié)束算法結(jié)束時(shí)沒(méi)有溢出的結(jié)點(diǎn)時(shí)沒(méi)有溢出的結(jié)點(diǎn).因此該算法是正確的因此該算法是正確的.分塊分塊L L列表的實(shí)現(xiàn)列表的實(shí)現(xiàn)如果用鏈表，可以只占用如果

50、用鏈表，可以只占用O(n)的空間。的空間。在內(nèi)存不緊張的情況下，也完全可以用在內(nèi)存不緊張的情況下，也完全可以用無(wú)序數(shù)組，時(shí)間效率不比鏈表差無(wú)序數(shù)組，時(shí)間效率不比鏈表差,雖然空雖然空間是間是O(n2)的的.無(wú)序數(shù)組在刪除的時(shí)候，可以用無(wú)序數(shù)組在刪除的時(shí)候，可以用:Delete(i)lai anlDec(n)更多的改進(jìn)更多的改進(jìn)回顧一下上面兩個(gè)算法的正確性回顧一下上面兩個(gè)算法的正確性:1).h是一個(gè)合法的高度函數(shù)是一個(gè)合法的高度函數(shù) Gf不存在增廣路不存在增廣路2).同一結(jié)點(diǎn)同一結(jié)點(diǎn)h值保證遞增值保證遞增 重標(biāo)號(hào)后沒(méi)有可行弧進(jìn)入結(jié)點(diǎn)重標(biāo)號(hào)后沒(méi)有可行弧進(jìn)入結(jié)點(diǎn) 列表列表L永遠(yuǎn)拓?fù)溆行蛴肋h(yuǎn)拓?fù)溆行騌elabel-to-front(highest-relabel)算法正確算法正確.也就是說(shuō)也就是說(shuō),只要滿足只要滿足1).2).兩條兩條,h的值具體怎么變的值具體怎么變化并不重要化并不重要.更多的改進(jìn)更多的改進(jìn)可以發(fā)現(xiàn)可以發(fā)現(xiàn),每當(dāng)重標(biāo)號(hào)操作被執(zhí)行每當(dāng)重標(biāo)號(hào)操作被執(zhí)行,該結(jié)點(diǎn)該結(jié)點(diǎn)的當(dāng)前弧的位置就被重置的當(dāng)前弧的位置就被重置,同時(shí)這個(gè)結(jié)點(diǎn)同時(shí)這個(gè)結(jié)點(diǎn)被往前提被往前提,然后這個(gè)結(jié)點(diǎn)后面的結(jié)點(diǎn)又全然后這個(gè)結(jié)點(diǎn)后面的結(jié)點(diǎn)又全部得被