Dinic算法基礎(chǔ)

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)。所以所有前