Dinic算法基礎(chǔ)_第1頁
Dinic算法基礎(chǔ)_第2頁
Dinic算法基礎(chǔ)_第3頁
Dinic算法基礎(chǔ)_第4頁
Dinic算法基礎(chǔ)_第5頁
免費(fèi)預(yù)覽已結(jié)束,剩余7頁可下載查看

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、一、引言圖論這門古老而又年輕的學(xué)科12在信息學(xué)競(jìng)賽中占據(jù)了相當(dāng)大的比重。 其中, 網(wǎng)絡(luò)流算法經(jīng)常在題目中出現(xiàn)。網(wǎng)絡(luò)流涵蓋的知識(shí)非常豐富,從基本的最小割最大流定理到網(wǎng)絡(luò)的許多變形再到最高標(biāo)號(hào)預(yù)流推進(jìn)的六個(gè)優(yōu)化等等,同學(xué)們?cè)谄綍r(shí)需要多多涉獵這方面的知識(shí),不斷積累,才能應(yīng)對(duì)題目的各種變化。隨著信息學(xué)競(jìng)賽的不斷發(fā)展,其題目的難度以及考察范圍都不斷增大?,F(xiàn)在,對(duì)于一些新出現(xiàn)的題目,僅僅掌握最樸素的網(wǎng)絡(luò)流算法并不足以解決問題。本文針對(duì)一些數(shù)據(jù)規(guī)模比較大的網(wǎng)絡(luò)流題目詳細(xì)介紹了基于分層思想的 3 個(gè)網(wǎng)絡(luò)流算法,并通過列舉和比較說明了其在解題中的應(yīng)用,而對(duì)一些基礎(chǔ)的知識(shí),如最小割最大流定理等,沒有作具體闡釋,大

2、家可以在許多其他網(wǎng)絡(luò)流資料中找到。二、預(yù)備概念22.1剩余圖的概念給定一個(gè)流量網(wǎng)絡(luò) Gi=(Ei,Vi)、源點(diǎn) s、匯點(diǎn) t、容量函數(shù) c,以及其上的流量函數(shù)f f。 我們這樣定義對(duì)應(yīng)的剩余圖 G2=(E2M):剩余圖中的點(diǎn)集與流量網(wǎng)絡(luò)中的點(diǎn)集相同,即 V2=Vi。對(duì)于流量網(wǎng)絡(luò)中的任一條邊3(u,v)wEi,若f(u,v)c(u,v)f(u,v)0f(u,v)0 那么邊(v,u)wE2,這條邊在剩余圖1i圖論這門學(xué)科的誕生始于 i8 世紀(jì)歐拉證明了七橋問題,發(fā)表依據(jù)幾何位置的解題方法一文。但圖論的真正發(fā)展是從 20 世紀(jì)五六十年代開始的。所以說,圖論是一門既古老又年輕的學(xué)科。2本文對(duì)一些基本的

3、理論,如最大流最小割定理等,不做闡述,讀者可以參閱相關(guān)網(wǎng)絡(luò)流資料。3本文中所有涉及到的邊若無指明均為有向邊。中的權(quán)值為 g(v,u)g(v,u)= =f(u,v)f(u,v)。我們可以發(fā)現(xiàn),流量網(wǎng)絡(luò)中的每條邊在剩余圖中都化作一條或二條邊。剩余圖中的每條邊都表示在原流量網(wǎng)絡(luò)中能沿其方向增廣。剩余圖的權(quán)值函數(shù) g(a,b)g(a,b)表示在流量網(wǎng)絡(luò)中能夠沿著 a a 到 b b 的方向增廣大小為 g(a,b)g(a,b)的流量。 所以在剩余圖中,從源點(diǎn)到匯點(diǎn)的任意一條簡(jiǎn)單路徑4都對(duì)應(yīng)著一條增廣路,路徑上每條邊的權(quán)值的最小值即為能夠一次增廣的最大流量。2.2頂點(diǎn)的層次在剩余圖中,我們把從源點(diǎn)到點(diǎn) u

4、 的最短路徑長(zhǎng)度稱作點(diǎn) u 的層次,記為level(u)olevel(u)o 源點(diǎn)的層次為 0o 在下面這張剩余圖中:每個(gè)點(diǎn)旁邊的數(shù)字即表示該點(diǎn)在圖中的層次2.3層次圖的概念我們這樣定義層次圖 G3=(V3,E3):對(duì)于剩余圖 G2=(V2,E2)中的一條邊(u,v)(u,v), ,當(dāng)且僅當(dāng) level(u)level(u)+ +1 1=level(v)=level(v)時(shí),邊(u,v)wE3;V3=u|E3中有邊與 u 相連直觀地講,層次圖是建立在剩余圖基礎(chǔ)之上的一張“最短路圖”。從源點(diǎn)開4簡(jiǎn)單路徑:路徑中不存在重復(fù)的頂點(diǎn)或邊始,在層次圖中沿著邊不管怎么走,經(jīng)過的路徑一定是終點(diǎn)在剩余圖中的最

5、短路2.4阻塞流的概念在流量網(wǎng)絡(luò)中存在一可行流 f,當(dāng)該網(wǎng)絡(luò)的層次圖 G3中不存在增廣路時(shí),我們稱流函數(shù) f f 為層次圖 G3的阻塞流。三、最短路徑增值算法(MPLA)的步驟及復(fù)雜度分析算法步驟之前我們講到的層次圖將被應(yīng)用在最短路徑增值算法中。首先,我們看一下最短路徑增值算法的步驟:1、初始化流量,計(jì)算出剩余圖2、根據(jù)剩余圖計(jì)算層次圖。若匯點(diǎn)不在層次圖內(nèi),則算法結(jié)束3、在層次圖內(nèi)不斷用 bfs 增廣,直到層次圖內(nèi)沒有增廣路為止4、轉(zhuǎn)步驟 2算法中,2、3 步被循環(huán)執(zhí)行,我們將執(zhí)行 2、3 步的一次循環(huán)稱為一個(gè)階段每個(gè)階段中,我們首先根據(jù)剩余圖建立層次圖,然后不斷用 bfs 在層次圖內(nèi)增廣,尋

6、找阻塞流。增廣完畢后,進(jìn)入下一個(gè)階段。這樣不斷重復(fù),直到匯點(diǎn)不在層次圖內(nèi)出現(xiàn)為止。匯點(diǎn)不在層次圖內(nèi)意味著在剩余圖中不存在一條從源點(diǎn)到匯點(diǎn)的路徑, 即沒有增廣路。在程序?qū)崿F(xiàn)的時(shí)候, 層次圖并不用被“建”出來, 我們只需對(duì)每個(gè)頂點(diǎn)標(biāo)記層次,增廣的時(shí)候,判斷邊是否滿足 level(u)level(u)+ +1=1=level(v)level(v)這一約束即可。定理的證明定理:又 t t 于有 n n 個(gè)點(diǎn)的流量網(wǎng)絡(luò),在最短路徑增值算法中,最多有n n 個(gè)階段。也就是說,在算法中層次圖最多被建立 n 次。證明這個(gè)定理有助于我們進(jìn)行算法復(fù)雜度分析。證明:在建立完層次圖以后,假設(shè)從源點(diǎn)到匯點(diǎn)的最短路徑長(zhǎng)度

7、為 k,我們將層次圖中所有的點(diǎn)分到 k+1 個(gè)集合中,第 i 個(gè)集合為頂點(diǎn) u|level(u)=i-1,如下圖所示:層次為 0 0 的頂點(diǎn)集合f)層次為 1 1 的頂點(diǎn)集合A層次為 2 2 的頂點(diǎn)集合.層次為 k-1k-1 的頂點(diǎn)集合層次為 k k 的頂點(diǎn)集合在剩余圖中,存在著 2 類邊第一類:從第 i i 個(gè)集合中的頂點(diǎn)連到第 i i+1(1+1(1wiwk)wiwk)個(gè)集合中的頂點(diǎn)第二類:從第 i(1wiwk+1)i(1wiwk+1)個(gè)集合中的頂點(diǎn)連到第 j(1wjwi)j(1wjwi)個(gè)集合中的頂點(diǎn)在層次圖中,只存在第一類邊,這是由層次圖的性質(zhì)決定的。我們所要找的增廣路中的邊也必定是第

8、一類邊。當(dāng)我們對(duì)一條增廣路徑增廣后,會(huì)刪除一條或多條增廣路中的飽和邊,也就是第一類邊;而同時(shí)會(huì)在剩余圖中加入一些與增廣路徑中的邊反向的邊。這些新加入的邊一定是第二類邊。如下圖所示,在剩余圖(a)中,找到一條從左向右的增廣路徑,能夠增廣的流量大小為 2。增廣后的結(jié)果是剩余圖(b)??梢园l(fā)現(xiàn),在剩余圖(a)里面,中間一條紅色第一類邊在增廣后飽和而被刪除了,同時(shí),在剩余圖(b)中,新增了 2 條綠色的第二類邊。522 2 市占源點(diǎn)點(diǎn)剩余圖(b)(b)當(dāng)我們?cè)趯哟螆D中找到阻塞流之后,層次圖中就不存在從第一個(gè)集合一步一步往下走,最后達(dá)到第 k+1 個(gè)集合的長(zhǎng)為 k 的路徑了。而此時(shí)不在層次圖中的邊都是第

9、二類邊。我們可以發(fā)現(xiàn),這個(gè)時(shí)候在剩余圖中的最短路徑一定是這樣:從源點(diǎn)開始,往下一步一步走,走到某個(gè)集合后沿著第二類邊向上退至某個(gè)集合,源點(diǎn)剩余圖(a)(a)匯點(diǎn)再繼續(xù)一步一步向下走,到某個(gè)集合又向上退,直到走到匯點(diǎn)。因?yàn)楸厝粫?huì)經(jīng)過第二類邊,而經(jīng)過的第一類邊的數(shù)量=k,所以路徑總長(zhǎng)度一定大于 k0這即是下一個(gè)階段的最短路徑長(zhǎng)度。由此,我們得出了一個(gè)結(jié)論:結(jié)論:層次圖中增廣路徑長(zhǎng)度隨階段而嚴(yán)格遞增。因?yàn)樵鰪V路徑長(zhǎng)度最短是 1,最長(zhǎng)是 n-1,再算上匯點(diǎn)不在層次圖內(nèi)的最后一次,層次圖最多被建造 n 次,所以最短路徑增值算法最多有 n 個(gè)階段。證畢。3.3復(fù)雜度分析建造層次圖的復(fù)雜度分析我們將復(fù)雜度分

10、析分為建層次圖和找增廣路兩部分討論。前面已經(jīng)證明了,在最短路徑增值算法中,最多建 n 個(gè)層次圖,每個(gè)層次圖用 bfs一次遍歷即可得到。 一次bfs遍歷的復(fù)雜度為O(m)O(m), ,所以建層次圖的總復(fù)雜度雜度為為O(n*m)O(n*m)o o增廣復(fù)雜度分析我們首先分析在每一階段中找增廣路的復(fù)雜度。注意到每增廣一次,層次圖中必定有一條邊會(huì)被刪除。層次圖中最多有 m條邊,所以可以認(rèn)為最多增廣 m 次。在最短路徑增廣中,我們用 bfs 來增廣。一次增廣的復(fù)雜度為 O(m+n)O(m+n)。其中 O(m)O(m)為 bfs 的花費(fèi),O(n)O(n)為修改流量的花費(fèi)。所以在每一階段的復(fù)雜度為 O(m*(

11、n+m)=O(m2)這樣,得到找增廣路總的復(fù)雜度為 O(n*m2)最短路徑增值算法的總復(fù)雜度即為建層次圖的總復(fù)雜度與找增廣路的總復(fù)雜度之和,為 O(n*m2)。四、Dinic算法的步驟以及復(fù)雜度分析4.1算法步驟Dinic 算法的思想也是分階段地在層次圖中增廣。 它與最短路徑增值算法不同之處是:在 Dinic 算法中,我們用一個(gè) dfs 過程代替多次 bfs 來尋找阻塞流下面給出其算法步驟:1、初始化流量,計(jì)算出剩余圖2、根據(jù)剩余圖計(jì)算層次圖。若匯點(diǎn)不在層次圖內(nèi),則算法結(jié)束3、在層次圖內(nèi)用一次 dfs 過程增廣4、轉(zhuǎn)步驟 2在 Dinic 的算法步驟中,只有第三步與最短路徑增值算法不同。之后我

12、們會(huì)發(fā)現(xiàn),dfs 過程將會(huì)使算法的效率較之 MPLA 有非常大的提高下面是 dfs 的過程:ps;Whileoutdegree(s)0up.top;ifutifoutdegree(u)0設(shè)(u,v)為層次圖中的一條邊;pp,v;else從 p 和層次圖中刪除點(diǎn) u,以及和 u 連接的所有邊;else增廣 p(刪除了 p 中的飽和邊);令 p.top 為 p 中從 s 可到達(dá)的最后頂點(diǎn)endwhile在程序里,p 表示找到的增廣路徑,p.top 為路徑中的最后一個(gè)頂點(diǎn)。一開始,p中只有源點(diǎn)。整個(gè) While 循環(huán)分為 2 個(gè)操作。如果 p 的最后一個(gè)頂點(diǎn)為匯點(diǎn),也就是說找到了增廣路,那么對(duì) p

13、增廣,注意到增廣后一定有一條或多條 p 中的邊被刪除了。這時(shí),我們使增廣路徑后退至 p 中從源點(diǎn)可到達(dá)的最后一個(gè)頂點(diǎn)。如果 p 的最后一個(gè)頂點(diǎn)不為匯點(diǎn),那么觀察最后那個(gè)的頂點(diǎn) u。若在層次圖中存在從 u 連出的一條邊,比如(u,v),我們就將頂點(diǎn) v 放入路徑 p 中,繼續(xù) dfs 遍歷;否則,點(diǎn) u 對(duì)之后的 dfs 遍歷就沒有用了,我們將點(diǎn) u 以及層次圖中連到 u 的所有邊刪除,并且在 p 中后退一個(gè)點(diǎn)。Dfs 過程將會(huì)不斷重復(fù)這 2 個(gè)操作,直到從源點(diǎn)連出的邊全部被刪除為止。下面給出一個(gè) dfs 的圖例,圖中,紅邊代表找到的增廣路 p 中的邊。2 23 3增廣完畢找到一條增廣路后退至原

14、增廣路中從源點(diǎn)可到達(dá)的最遠(yuǎn)電源點(diǎn)對(duì)增廣路進(jìn)行增廣源點(diǎn)源點(diǎn)4.2復(fù)雜度分析和在最短路徑增值算法中的證明一樣,Dinic 算法最多被分為 n 個(gè)階段。這樣首先可以得到 Dinic 算法中建立層次圖的總復(fù)雜度仍是 O(n*m)O(n*m)。我們?cè)賮矸治?dfs 過程的總復(fù)雜度。在每一階段,將 dfs 分成 2 部分分析:ps;Whileoutdegree(s)0up.top;ifutifoutdegree(u)0設(shè)(u,v)為層次圖中的一條邊;pp,v;else從 p 和層次圖中刪除點(diǎn) u,以及和 u 連接的所有邊;else增廣 p(刪除了 p 中的飽和邊);令 p.top 為 p 中從 s 可到達(dá)

15、的最后頂點(diǎn);endwhile(1)修改增廣路的流量并后退的花費(fèi):(即為代碼中紅框?qū)?yīng)的部分)在 3.3.2 小節(jié)中我們講到過,在每一階段,最多增廣 m 次,每次修改流量的費(fèi)用為 O(n)O(n)0 0而一次增廣后在增廣路中后退的費(fèi)用也為O(n)oO(n)o 所以在每一階段,修改增廣路以及后退的復(fù)雜度為O(m*(n+n)=O(m*n)O(m*(n+n)=O(m*n)。(2)Dfs 遍歷時(shí)的前進(jìn)與后退5:(即為代碼中籃框?qū)?yīng)的部分)我們將用到 3.1 小節(jié)中的知識(shí)。在 dfs 遍歷時(shí),如果當(dāng)前路徑的最后一個(gè)頂點(diǎn)能夠繼續(xù)擴(kuò)展,則一定是沿著第一類邊向匯點(diǎn)前進(jìn)了一步。因?yàn)樵鰪V路徑長(zhǎng)度最長(zhǎng)為 n,所以最多連續(xù)前進(jìn) n 步后就會(huì)遇到匯點(diǎn)。在前進(jìn)的過程中,可能會(huì)遇到?jīng)]有邊能夠沿著繼續(xù)前進(jìn)的情況,這時(shí),我們將路徑中的最后一個(gè)點(diǎn)在層次圖中刪除并出棧60注意到每后退一次必定會(huì)刪除一個(gè)點(diǎn),所以后退的次數(shù)最多為 n次。在每一階段中,后退的復(fù)雜度為 O(n)O(n)。假設(shè)在最壞情況下,所有的點(diǎn)最后均被刪除,一共后退了 n 次,這也就意味著,有 n 次的前進(jìn)被“無情”地退了回來,這 n 次前進(jìn)操作都打了水漂。除去這 n 次前進(jìn)和 n 次后退,其余的前進(jìn)都對(duì)最后找到增廣路作了貢獻(xiàn)。增廣路最多找 m 次,每次最多前進(jìn) n 個(gè)點(diǎn)。所以所有前

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論