s-t Flow

所謂伊人,在水一方。溯洄從之,道阻且長;溯游從之,宛在水中央。《詩經.蒹葭》

Capacity Graph(Flow Network)

一張圖想成是水流管線圖。邊:水管,有向邊僅允許單向流動,無向邊得同時雙向流動。邊的權重:水管容量。點:水管接頭,附有特殊機器,可以控制流向與流量。點的權重:水管接頭容量。大家一般不考慮點的權重。

各條管線的流量數值與容量數值,以一斜線區隔,標記於旁,方便觀看。

水流流動時,必須遵守各條管線的方向限制,不得逆向流動。水流流動時,也必須遵守各條管線的容量限制,不得逾越容量限制。流量數值與容量數值一定是正值或零,不得為負值。

水流流動時,流速是穩定的、源源不絕的,流向與流量是可以調節的。水流流動時,只需注意各條管線的方向限制與容量限制。

「容量圖」只有容量資訊,沒有流量資訊。

s-t Flow

在圖上選定一個源點(source,標記為s)和一個匯點(sink,標記為t),源點灌水,匯點泄水,並控制水流從源點流至匯點,中途不得滲漏、不得淤滯。

s-t Flow以下簡稱為「流」。一個流便是由源點經管線至匯點的水流。一個流的流量,即是源點灌入的水流流量,同時也是匯點泄出的水流流量。

換句話說,源點出邊流量,加總起來,即是總流量;匯點入邊流量,加總起來,即是總流量。

「流」只有流量資訊,沒有容量資訊。

Maximum s-t Flow

「最大流」。給定一張圖,以及給定一個源點與一個匯點,所有可能的s-t Flow當中,流量最大者便是Maximum s-t Flow,可能會有許多個。

源點灌入大量的水,調整各條管線的流向與流量,讓匯點泄出的流量最多。

Minimum s-t Flow

「最小流」。一滴水都不流,管線裡都沒水,流量為零。

大家應該都懂,所以就討論到這裡了。

圖例:不屬於流的玩意

水流流到無法流動的地方,水流淤滯而無法流至匯點,不能稱作流。

圖例:合流、分流、交流

水流可以在任何點上合流、分流、交流。簡單來說,每個點之中,流入水量與流出水量,兩者相等。至於要怎麼分合都無所謂。

圖例:產生迴圈的流

產生迴圈的流,佔據管線容量,難以增加流量,是一種浪費。

圖例:源點與匯點在一起的流

感情很好的兩個點,內地裡波濤洶湧,表面上流量為零。

多個源點變成一個源點、多個匯點變成一個匯點

先前只討論一個源點和一個匯點,其實是因為多個源點可以化作一個源點、多個匯點可以化作一個匯點。當圖上有多個源點,就在圖上新增一個超級源點,連向這些源點,邊的容量都設定為無限大。如此一來,就可以只留下一個超級源點,並取消原本的源點了。匯點的道理亦同。

因此,在s-t Flow當中,多個源點和多個匯點可以改為一個源點和一個匯點,最後只討論一個源點和一個匯點就可以了。事情變得簡單多了。

點的容量變成邊的容量

先前提到大家一般不考慮點的容量,其實是因為點的容量可以化作邊的容量。把P點改成兩個點Pin和Pout,連入P點的邊變成連入Pin,由P點連出的邊變成由Pout連出,P點的容量替換成一條Pin到Pout的邊。

因此,在s-t Flow當中,點的容量可以改為邊的容量,最後只討論邊的容量就可以了。事情變得簡單多了。

多重的邊變成單獨的邊

無向圖,當兩點之間有多重的邊,就可以加總這些邊的容量,合併成單獨的邊;有向圖,當一點到另一點有多重的邊,就可以加總這些邊的容量,合併成單獨的邊。

因此,在s-t Flow當中,多重的邊可以改為單獨的邊,最後只討論「無向圖:兩點間僅有一條邊」、「有向圖:一點到另一點僅有一條邊」就可以了。事情變得簡單多了。

來回水流變成單向水流

兩點之間,兩條方向相反的有向邊,等量減少來向與回向的水流,不會影響總流量,也不會違背規則。

因此,在s-t Flow當中,來回水流可以變成單向水流,最後只要從中選擇一條邊來流動就可以了。事情變得簡單多了。

無向邊變成有向邊

無向邊得同時雙向流動。一條無向邊可以改為兩條方向相反的有向邊,可是必須共用容量。

因為來回水流可以變成單向水流,所以上述兩條方向相反的有向邊,其實不必共用容量,宛如普通的有向邊。

因此,在s-t Flow當中,一條無向邊可以變成兩條方向相反的有向邊,最後只討論有向邊就可以了。事情變得簡單多了。

Max-Flow Min-Cut Theorem

一條涓流的流量與瓶頸

水從源點流至匯點,中途不會滲漏、不會淤滯。源點流至匯點的小小涓流,其流動路徑當中,每一條邊的流量,都是涓流的流量。

水流流動必須遵守管線容量限制。源點流至匯點的小小涓流,其流量的瓶頸,會是流動路徑當中,容量最低的一條邊。

一個流的總流量與瓶頸(一)

水從源點流至匯點,中途不會滲漏、不會淤滯。現在把圖上的點,依地理位置劃分作兩區,一區鄰近源點,另一區鄰近匯點。「源點流至匯點的總流量」等於「源點區流入到匯點區的總流量」減去「匯點區流回到源點區的總流量」。無論是哪一種分區方式,都有這種性質。

水流流動必須遵守管線容量限制。「源點區流入到匯點區的總流量」會小於等於「源點區橫跨到匯點區的總容量」。反方向亦同。

也就是說,源點流至匯點的流,其總流量的瓶頸,會是「源點區橫跨到匯點區的總容量」最低的一種分區方式。

一個流的總流量與瓶頸(二)

【關於s-t Cut,請見本站文件「s-t Cut」。】

方才的分兩區方式有點籠統,很難定義誰鄰近源點,誰鄰近匯點,因此計算學家嘗試以s-t Cut來取代方才的說法,希望藉由s-t Cut把事情說得更嚴謹一些。然而事情也稍微變得複雜了。

水從源點流至匯點,中途不會滲漏、不會淤滯。現在把圖上的點,利用s-t Cut的概念劃分作兩側,一側包含源點,另一側包含匯點。「源點流至匯點的總流量」等於「源點側流入到匯點側的總流量」減去「匯點側流回到源點側的總流量」。無論是哪一種劃分方式,都有這種性質。

水流流動必須遵守管線容量限制。「源點側流入到匯點側的總流量」小於等於「源點側橫跨到匯點側的總容量」。反方向亦同。

也就是說,源點流至匯點的流,其總流量的瓶頸,會是「源點側橫跨到匯點側的總容量」最低的一種劃分方式。也就是容量圖的Minimum s-t Cut。

Max-Flow Min-Cut Theorem

「最大流最小割定理」。「最大st流」等於「最小st割」。

重點在於瓶頸。儘量增加流量,填滿剩餘容量,直到遭遇瓶頸。

打個比方來說,在一個裝水的塑膠袋底部戳洞,水就會流出來;戳越多洞,水就流出的越多。這表示水一旦有隙可乘,就一定會源源而來、滔滔而至,乃增加流量。水一旦無隙可乘,流量達到上限,此刻就是最大流了。

要找最大流,可以運用「最大流最小割定理」,讓水流不斷地鑽空隙流至匯點。無法再找到空隙,就是極限了,就是最大流了。

Maximum s-t Flow: Ford–Fulkerson Algorithm (Augmenting Path Algorithm)

不積跬步,無以至千里。不積小流,無以成江海。《荀子》

用途

給定一張有向圖,並給定源點、匯點,找出其中一個最大流。

涓流【註:此概念目前尚未有專有名詞】

一個流是由許多條涓流逐漸聚集而成的。我們可以用一條一條的涓流,累積成最大流。

溯洄沖減【註:此概念目前尚未有專有名詞】

然而有些涓流的路徑不理想,浪費了管線空間。有鑒於此,演算法作者設計了一個手法:溯洄沖減。流出第一條涓流之後,第二條涓流可以溯洄上一條流的部份路段,然後到達匯點。正流與逆流相互沖減的結果,使得相互交織的兩條涓流,成為兩條獨立的涓流。如此一來,就算涓流的路徑不理想,之後仍可靠溯洄沖減來調整路徑。

【註:涓流、溯洄、沖減這三個詞,是初次使用。我查字典後,覺得意義相近,而選用的。而且它們都是水字旁!】

自由選擇水量多寡和路線位置,藉以調整成不同的流。無論什麼情況,都能調整路徑,得到心目中的流。

溯洄沖減的概念可以用於許多地方。這裡列出一些相關問題,供各位練習。

UVa 10806 10380

Residual Graph

每次增加一條涓流,必須遵守管線容量限制。管線有剩餘空間、或者管線有溯洄沖減的機會,涓流才能流過管線。

一個便捷的整合方式是:管線的剩餘空間、再加上可供溯洄沖減的水量,稱作「剩餘容量Residual Capacity」;所有管線的剩餘容量,整體視作一張圖,稱作「剩餘圖Residual Graph」。

如此一來,涓流要進行流動,只要參考剩餘圖,遵守剩餘容量限制就可以了。

Augmenting Path

「擴充路徑」。剩餘圖上面一條源點到匯點的路徑。把握剩餘容量,把握溯洄沖減,找出一條源點到匯點的涓流路徑,就是一條擴充路徑。

擴充路徑是一條可以擴充總流量的路徑,擴充的流量可多可少。一般來說流量越多越好,到達瓶頸最好,能較快達到最大流。

擴充路徑的長度範圍是1到V-1(長度為0表示源點與匯點重疊)。當一條擴充路徑超過V-1條邊,則形成浪費管線容量的迴圈。此時應消除迴圈之後,才來作為擴充路徑。

演算法

不斷找擴充路徑,並擴充流量。直到沒有擴充路徑為止。

擴充路徑要怎麼找都可以。不一樣的擴充路徑,有機會產生不一樣的最大流。

所有擴充路徑總合起來,就是最大流。所有擴充路徑的流量總和,就是最大流流量。

導入「溯洄沖減」機制,藉以調整流動路徑。整合「容量限制」與「溯洄沖減」,創立「剩餘圖」、「擴充路徑」。最後返回「最大流最小割定理」,無論什麼情況,擴充路徑都能找出最大流。

整個過程當中,所有管線的剩餘容量的總和是固定不變的──源點往匯點方向的剩餘容量越來越少,匯點往源點方向的剩餘容量越來越多。

整個過程當中,不斷調整剩餘圖的勢力走向──以擴充路徑擴充流量,正方向減少剩餘容量,逆方向增加剩餘容量,源點與匯點之間的勢力差距越來越大。

時間複雜度

找一條擴充路徑,等同一次Graph Traversal的時間。

最差情況下,擴充路徑流量通通都是1,總共找到F條,F是最大流的流量。

圖的資料結構為Adjacency Matrix是O(V²F);圖的資料結構為Adjacency Lists是O((V+E)F),通常簡單寫成O(EF)。

如何記錄容量、流量、剩餘容量

剩餘圖是高度抽象概念,整合了管線容量限制、溯洄沖減機制。實作程式碼時,可以直接建立剩餘圖。

為了實現溯洄沖減,要是兩點之間,只有單獨一條有向邊,就添配一條反向邊,讓雙向都有邊;已經是兩條方向相反的有向邊,就不必更動。

每一條邊,容量是定值,流量與剩餘容量則有三種記錄方式。通常使用第三種方式。

第一種記錄方式。涓流經過管線,涓流流量累計到管線流量。

最初沒有水流:
flow(i, j) = 0;
flow(j, i) = 0;

一條涓流經過邊ij:
flow(i, j) += 流量;
flow(j, i) 保持不變;

一條涓流經過邊ij,又一條涓流溯洄沖減經過邊ji:
flow(i, j) += 流量1;
flow(j, i) += 流量2;

一條涓流經過邊ij,歸納為:
flow(i, j) += 流量;
flow(j, i) 保持不變;
residual(i, j) = capacity(i, j) - (flow(i, j) - flow(j, i));
residual(j, i) = capacity(j, i) - (flow(j, i) - flow(i, j));

第二種記錄方式。先前提到,兩條方向相反的有向邊,可以只讓一條邊擁有水流。沒有水流的那條邊,在此故意設定為負流量。

最初沒有水流:
flow(i, j) = 0;
flow(j, i) = 0;

一條涓流經過邊ij:
flow(i, j) += 流量;
flow(j, i) -= 流量;

一條涓流經過邊ij,又一條涓流溯洄沖減經過邊ji:
flow(i, j) = flow(i, j) + 流量1 - 流量2;
flow(j, i) = flow(j, i) - 流量1 + 流量2;

一條涓流經過邊ij,歸納為:
flow(i, j) += 流量;
flow(j, i) = -flow(i, j);
residual(i, j) = capacity(i, j) - flow(i, j);
residual(j, i) = capacity(j, i) - flow(j, i);

第三種記錄方式。第二種記錄方式的相反面向,主角改為剩餘容量。涓流經過管線,正方向剩餘容量減少,反方向剩餘容量增加。

最初沒有水流:
residual(i, j) = capacity(i, j);
residual(j, i) = capacity(j, i);

一條涓流經過邊ij:
residual(i, j) -= 流量;
residual(j, i) += 流量;

一條涓流經過邊ij,又一條涓流溯洄沖減,經過邊ji:
residual(i, j) = residual(i, j) - 流量1 + 流量2;
residual(j, i) = residual(j, i) + 流量1 - 流量2;

一條涓流經過邊ij,歸納為:
residual(i, j) -= 流量;
residual(j, i) += 流量;
flow(i, j) = capacity(i, j) - residual(i, j);
flow(j, i) = capacity(j, i) - residual(j, i);

找出一個最大流+計算最大流的流量

第三種紀錄方式顯然最好懂。

Maximum s-t Flow: Edmonds–Karp Algorithm (Shortest Augmenting Path Algorithm)

演算法

Augmenting Path Algorithm改良版。擴充路徑是源點到匯點的最短路徑(管線長度皆為1),並且擴充流量至瓶頸。這種方式可以避免浪費管線空間,避免反覆地溯洄沖減,更快找到最大流。

不斷找最短擴充路徑,直到找不到為止,即得最大流。
最多找VE次就能達到最大流。

達到最大流,需要的最短擴充路徑數量。
(Edge Labeling with Shortest Distance)

剩餘圖的每一條邊,皆標記一個距離數值,數值大小是源點到該邊的最短距離。

以最短路徑擴充流量至瓶頸,某些邊的距離數值會增加,沒有任何一條邊的距離數值會減少。宏觀來看,距離數值與日俱增。

擴充路徑是最短路徑。瓶頸之處,新增的反向邊,比起原先的正向邊,距離數值至少多一。從彼端繞過來一定比較遠。

瓶頸正向邊:距離數值增加,變成無限大。(水滿了,從剩餘圖之中消失。)
瓶頸反向邊:距離數值不變,比正向邊至少多一。(原先就有反向邊。)
      距離數值增加,比正向邊至少多一。(原先沒有反向邊,新增反向邊。)
 其餘的邊:距離數值不變。(瓶頸斷掉,但是有替代路線。或者尚未遭遇瓶頸。)
      距離數值增加。(瓶頸斷掉,繞遠路。)

甲、最差情況下,每次擴充流量,整體距離數值只增加1。乙、圖上總共E條邊,每條邊的距離數值範圍為0到V-1。因此至多VE條最短擴充路徑,就能達到最大流。

達到最大流,需要的最短擴充路徑數量。
(Vertex Labeling with Shortest Distance)

剩餘圖的每一個點,皆標記一個距離數值,數值大小是源點到該點的最短距離。

每次以最短路徑擴充流量至瓶頸之後,最短路徑上的點的距離數值不見得會增加;源點到該點的所有最短路徑們通通截斷之後,距離數值才會增加。因此這種方式估計不出結果!

時間複雜度

以BFS尋找O(VE)條擴充路徑的時間。

圖的資料結構為Adjacency Matrix是O(V³E);圖的資料結構為Adjacency Lists是O((V+E)VE),通常簡單寫成O(VE²)。

UVa 820 10330 10779 563 10511 10983

Maximum s-t Flow: Dinitz' Algorithm (Blocking Flow Algorithm)

抽刀斷水水更流,舉杯消愁愁更愁。《李白.宣州謝朓樓餞別校書叔雲》

演算法

Shortest Augmenting Path Algorithm改良版。一口氣找到一樣長的最短擴充路徑們。

重覆以下動作最多V-1次,直到無法擴充流量:
1. 計算residual graph各點到源點(匯點)的最短距離。
2. 建立admissible graph。
3. 尋找blocking flow,並擴充流量。

Admissible Graph

剩餘圖上面,以源點(匯點)作為起點,計算源點(匯點)到每一點的最短距離。

剩餘圖上面,一條源點往匯點方向的邊、兩端點最短距離相差一,稱作「容許邊Admissible Edge」。所有容許邊,整體視作一張圖,稱作「容許圖Admissible Graph」。

容許圖是有向無環圖(DAG)、分層圖(Level Graph)。容許圖可以畫成一層一層的模樣,只有相鄰的層有邊。

容許圖就是剩餘圖的「最短路徑圖」。

容許圖上面,任意一條源點到匯點的路徑,都是最短擴充路徑。藉由容許圖,可以迅速找到一樣長的最短擴充路徑們。

Blocking Flow

容許圖上面,一個源點到匯點的流,無法再擴充流量,稱作「阻塞流」,通常有許多種,也不必是最大流。

容許圖上面,逐次找到一樣長的最短擴充路徑們,並且每次都讓擴充的流量到達瓶頸,直到找不到為止;整體形成阻塞流。

演算法:找出一個阻塞流

容許圖上面,尋找最短擴充路徑,不必溯洄沖減。溯洄沖減會增加路徑長度,最後得到的不是最短擴充路徑。

由源點隨意往匯點走,若遇到死胡同,就重頭開始走,下次避免再走到死胡同。若順利走到匯點,就形成一條最短擴充路徑,並且擴充流量。

改由匯點隨意往源點走,就不會遇到死胡同。

一條最短擴充路徑,至少有一條邊是瓶頸。容許圖最多只有E條邊能作為瓶頸,所以一個阻塞流最多只有E條最短擴充路徑。

從源點走到匯點並擴充流量需時O(V),最多有O(E)條最短擴充路徑,所以找出一個阻塞流的時間複雜度是O(VE)。

另外,使用「Link–Cut Tree」記錄容許圖,時間複雜度可以加速到O(ElogV)。

達到最大流,需要的阻塞流數量。
(Vertex Labeling with Shortest Distance)

前面章節利用Vertex Labeling with Shortest Distance估計不出結果,這裡卻可以。

剩餘圖上面,以阻塞流擴充流量,就斷絕了所有一樣長的最短擴充路徑。

容許圖上面,所有源點到匯點的最短路徑們都阻塞了。剩餘圖上面,源點到匯點的最短距離會增加,下次的最短擴充路徑會更長;擴充流量而新增的反向邊,也不會減少源點到匯點的距離。

擴充路徑的長度範圍是1到V-1(長度為0表示源點與匯點重疊)。因此最多找V-1次阻塞流,就一定沒有擴充路徑了。

時間複雜度

找一個阻塞流需時O(VE),找O(V)次,時間複雜度O(V²E)。

UVa 10546

Maximum s-t Flow: Karzanov's Algorithm (Preflow Algorithm)

專著

《Combinatorial Algorithms: Enlarged Second Edition》。

這本專著有詳細圖解。

演算法

Blocking Flow Algorithm改良版。只改善阻塞流的演算法。

容許圖上面,尋找阻塞流,至多E條擴充路徑,時間複雜度O(E(V+E)),通常簡單寫成O(VE)。「從頭重走E次」改成「中途回溯再前進」,時間複雜度降為O(V²+E),通常簡單寫成O(V²)。

Backtracking(不是DFS)走訪容許圖,依照拓樸順序。從源到匯,逐邊送水,逐點積水。針對當前點:

一、若出邊未滿:甲、若出邊可以增加水量(此點積水充足),則前進。乙、若出邊無法增加水量(此點積水用罄),則回溯。

二、若出邊皆滿(此點積水過剩),則入邊依照LIFO順序減少水量(此點積水回流),直到此點出入水量相等(此點積水為零)。往回追蹤檢查。回溯,永不走訪此點,永不走訪減少水量的入邊。

時間複雜度:增加水量

一、灌到滿:最多E次。

二、灌不滿:最多(V-1)+(V-2)+...+1次。

解釋一下灌不滿的次數。引進新概念「排水」:一個點,每條出邊依序送水。灌滿一條出邊,繼續灌滿下一條出邊,直到積水用罄、積水過剩。最後那一條出邊,可能灌不滿、可能恰好灌到滿。

排水一次,至多灌不滿一次。

考慮拓樸順序。第零點排水,源點積水無限大,所有出邊灌到滿,不在討論範圍。第一點排水,後續V-2點都可能發生積水回流至第一點,導致第一點再度排水。第一點至多排水V-1次,至多灌不滿V-1次。第二點則是V-2次。第三點則是V-3次。以此類推。

Backtracking僅僅調動了送水順序。灌不滿的次數仍然一樣多。

時間複雜度:阻塞流

一、容許圖:一次Graph Traversal的時間。

二、前進與回溯:三的兩倍。

三、增加水量:最多E+(V-1)+(V-2)+...+1次。

四、減少水量:最多E次。

時間複雜度O(V²+E),通常簡單寫成O(V²)。

時間複雜度

找一個阻塞流需時O(V²),最多找O(V)次,時間複雜度O(V³)。

名詞解釋

原始論文的描述方式略有不同。

一、分層圖推廣成有向無環圖。
二、預先讓源點排水,預先讓源點所有出邊灌到滿。
  演算法過程當中,不再處理源點,節省時間。
三、Backtracking,不採用遞迴,而是採用迴圈。
  每個點各自建立queue,儲存出邊剩餘容量,以便前進。
  每個點各自建立stack,儲存入邊流量,以便回溯。
四、前進、回溯,分成兩波,輪流進行。
  積水充足,按照拓樸順序接連前進,直到沒有任何一點能夠前進。
  積水過剩,按照拓樸逆序接連回溯,直到沒有任何一點積水過剩。
stack            入邊流量
queue            出邊剩餘容量
push             出邊增加水量
balance          入邊依照LIFO順序減少水量,直到此點出入水量相等
excess           所有入邊水量減掉所有出邊水量
flow             源匯以外每一點出入水量相等
preflow          源匯以外有些點出入水量不相等
blocking flow    源點到匯點的所有路徑都出現瓶頸
blocking preflow 任一點到匯點的任一條路徑出現瓶頸

Maximum s-t Flow: Goldberg–Tarjan Algorithm (Push–Relabel Algorithm)

🕛Preflow

想像一下:模仿針筒注射、發射水槍。源點放入足夠水量,然後用力推擠源點,讓源點的水一股作氣鑽過整張圖,從匯點噴出水流。

受限於管線容量瓶頸,水流流量是有上限的。水鑽過整張圖的路線,就是一個最大流。匯點噴出的水流流量,就是最大流的流量。

然而電腦程式無法直接實現「一股作氣鑽過整張圖」,電腦程式只能一步一步計算。我們只好「一點接著一點慢慢送水」:首先源點送水到其它中繼點,然後中繼點送水到其他中繼點,直到匯點。

🕐Excess

為了實現「一點接著一點慢慢送水」的想法,讓圖上每個點都可以暫時儲存水,稱作「積水點」。儲存水量,稱作「積水量」。一個點收到水之後,可以暫時儲存,可以隨時送水到其他點。

建立「積水點」和「積水量」之後,水一直存在、不會消失。即便送水送錯地方,也可以往回送水,調校水流流向。

以「積水點」和「積水量」設計最大流演算法:
一、源點的積水量,設定成無限大。
二、源點送水到各點,慢慢送水到匯點,送水順序隨意。
三、遇到管線容量瓶頸,多餘的水量將停留在點上。
四、最後能夠送到匯點的水量,就是最大流的流量。

🕑Residual Capacity

圖上每條邊都擁有流量,流量大於等於零、小於等於容量。

正向邊的流量與容量差距、反向邊的流量(溯洄沖減),兩者相加,得到「剩餘容量」。

以「剩餘容量」設計最大流演算法:
一、根據剩餘容量,盡量灌滿流量。模仿針筒注射、發射水槍。
二、利用剩餘容量,調校水流流向。送水送錯地方,可以往回送水。

🕒Height

為了實現「一點接著一點慢慢送水」的想法,必須確保流向正確,避免來回送水,避免繞圈送水。

引入「水往低處流」的想法。讓圖上每個點都有「高度」,由高往低送水。

以「水往低處流」設計最大流演算法:
一、由源點漫溢:源點是最高點。
二、朝匯點聚集:匯點是最低點。
三、源點往匯點:其他點比源點低、比匯點高。
四、避免繞圈送水:不能送水到一樣高的鄰點。只能送水到更低的鄰點。

再引入「一點接著一點慢慢送水」的想法。只有「高度」剛好低一層的鄰點,才可以送水。

以「一點接著一點慢慢送水」設計最大流演算法:
一、高度可以安排為:以匯點為終點的最短路徑長度,作為高度。
二、送水規則可以制定為:一個點只能送水到「剛好低一層」的鄰點。

🕓Admissible Edge

以剩餘容量、高度,制定水流的遵行方向。

一條邊,剩餘容量大於零、高度減少一,形成「容許邊」。

出現新麻煩:無法調校水流流向。

🕔Relabel

為了實現「調校水流流向」的想法,讓圖上每個點都可以「抬高」。

甚至最初將高度通通設為零,放任圖上各點自由抬高。

🕕Push

一個積水點想要「送水」到鄰點,那就抬高積水點,比鄰點高一層。如果流量已滿,那就抬更高。

一個積水點想要「送水」到鄰點,需要注意三件事:一、點的積水量。盡量排空水量。二、鄰邊的剩餘容量。盡量灌滿流量。三、鄰點的高度。高度低一層。

🕖Retreat

積水點下游遭遇瓶頸(甚至沒有管線),導致積水點水洩不通、積水難消,那就繼續抬高、往回送水,稱作「撤退」。

🕗Discharge

為了實現「一點接著一點慢慢送水」的想法,讓圖上每個點都可以「排水」。不斷抬高,不斷送水,把水排乾。

排水可以避免一鼓作氣送水到最低點,結果發現送錯方向,又從最低點一路撤退回到原點。排水可以大幅減少送水次數。

一個積水點有許多鄰點。首先抬高積水點,稍高於最低鄰點,送水到最低鄰點,盡量灌滿流量。如果仍有積水,再度抬高積水點,稍高於次低鄰點,送水到次低鄰點,盡量灌滿流量。以此類推,直到積水用罄。

🕘Complete Retreat

當水量過剩,許多水無處可去。繼續抬高每個點,直到比源點高,讓多餘的水回歸源點──剛好作為演算法的閉幕。最後圖上的水流流動情形就是最大流。

🕙Source Discharge

抬高過程當中,源點與鄰點不斷來回送水,浪費時間。預先讓源點強制送水到所有鄰點,並且大幅抬高源點,節省時間。

🕚Source Height

擴充路徑長度最多V-1。源點高度與匯點高度最多相差V-1。如果相差超過V-1,源點絕對無法送水到匯點。

預先讓源點高度固定為V-1,匯點高度固定為0,其他點自由抬高。V是圖上的點數。

小結

想讓水「一股作氣鑽過整張圖」,電腦卻只能「一點接著一點慢慢送水」。只好創立「積水點」,引入「水往低處流」的想法,以匯點為終點的最短路徑長度作為「高度值」,迫使水流向匯點。創立「抬高」,以便調校水流流向。創立「排水」,避免一鼓作氣送水到最低點。多餘的水,無法到達匯點,藉由抬高,順利回歸源點。

方才設計的最大流演算法:
一、由源點漫溢:源點高度固定為V-1。
二、朝匯點聚集:匯點高度固定為0。
三、前往匯點:抬高一個點,比匯點高。
四、回歸源點:抬高一個點,比源點高。
五、避免繞圈送水:不能送水到一樣高的鄰點。只能送水到剛好低一層的鄰點。
六、調校水流流向:抬高一個點,比鄰點高一層,以便送水到剛好低一層的鄰點。

接下來開始詳細列出演算法內容。

Push

積水點送水到鄰點。

一、積水點不是源點和匯點。(源點已排水,匯點只收水。)
二、積水點仍有水。
三、積水點到鄰點仍有剩餘容量。
四、積水點到鄰點剛好下降一層。

Relabel

積水點抬高:直到可以送水至鄰點。

Discharge

積水點排水:不斷push和relabel,直到沒水。

Height

以匯點為終點的最短路徑長度,作為高度。

可以省略不做。一律設為0,不影響結果。然而會額外抬高許多次,浪費時間。

Preflow【原始論文將Source Discharge叫做Preflow】

一、源點高度固定為V-1,匯點高度固定為0。

二、源點積水量無限大。

三、源點強制送水到所有鄰點,無視高度。

可以省略不做。限制源點高度低於V,不影響結果。然而會額外抬高許多次,浪費時間。

演算法:一直找任意積水點送水或抬高
(Push–Relabel Algorithm)

1. height。(可省略)
2. preflow。(可省略,但是要限制源點高度低於V。)
3. 不斷push或relabel,次序隨意,直到無法進行為止。

Preflow Algorithm改良版。隨時調整高度值、容許圖。容許圖從靜態變成動態(嚴格來說是自適應adaptive)。

僅以兩種「點對鄰點」的動作push、relabel,求得最大流。十分精采!

時間複雜度

我們針對push、relabel的次數下手。

relabel抬高:源點高度設為V-1,匯點高度設為0。最差情況下,除源點匯點,最高點升到了2V-3、最低點升到了V。

一個點O(V)次,所有點O(V²)次。一次O(deg(vᵢ)),總共O(VE)。

saturating push灌到滿:一條邊,兩個端點逐漸升高,高度範圍為0到2V-3,高度相差一才能送水,一種高度最多送水一次。

一條邊O(V)次,所有邊O(VE)次。一次O(1),總共O(VE)。

non-saturating push灌不滿:同上,但是端點可從鄰點補充水量,最多補充V-2次。一種高度最多送水V-1次。

一條邊O(V²)次,所有邊O(V²E)次。一次O(1),總共O(V²E)。

時間複雜度O(V²E),受限於non-saturating push。

演算法:積水點以任意順序排水

1. height。(可省略)
2. preflow。(可省略,但是要限制源點高度低於V。)
3. 不斷discharge,次序隨意,直到無法進行為止。

改成discharge,效率沒有顯著提升。

演算法:積水點以FIFO順序排水
(FIFO Push–Relabel Algorithm)

1. 建立一個queue,塞入積水點(不包括源點匯點),積水點不重複。
2. queue不斷彈出點,進行discharge,直到queue無點。
   當discharge產生新的積水點,而且queue沒有這個積水點,就塞入queue。

relabel抬高:時間複雜度同前。

saturating push灌到滿:時間複雜度同前。

non-saturating push灌不滿:援引Preflow Algorithm的分析技巧。所有邊O(V³)次。總共O(V³)。

時間複雜度降為O(V³)。

演算法:一直找最高的積水點排水
(Highest-Label Push–Relabel Algorithm)

宛如一口氣尋找所有擴充路徑。

時間複雜度降為O(V²sqrtE)。

加速技巧:Blocking Flow

容許圖,源點到匯點連通,才能送水。

容許圖,鄰點高度差一。想要保持連通,每種高度缺一不可。

圖上各點不斷抬高。任何一種高度,一旦出現又消失,表示更高點到更低點不連通,形成阻塞流。更高點無法送水到更低點。更高點即將全面撤退。更高點大可不必再排水、抬高、送水,以節省時間。

建立高度直方圖,隨時判斷連通。一旦不連通,拋棄更高點,使之無作為。中文網路稱作「gap优化」。

注意到,這個技巧只能求得最大流流量,無法求得最大流。

Maximum s-t Flow: Ahuja–Orlin Algorithm (Distance-directed Augmenting Path Algorithm)

專著

《Network Flows: Theory, Algorithms, and Applications》。

書上描述為Improved Shortest Augmenting Path Algorithm。

演算法:擴充路徑版本
(Distance-directed Augmenting Path Algorithm)

Push–Relabel Algorithm改良版。放棄逐點送水,重啟擴充路徑。

DFS走訪容許圖,尋找擴充路徑。若遇到死胡同,就relabel、retreat,另覓路徑。若順利走到匯點,就形成一條擴充路徑,並且擴充流量。

擴充路徑,各點高度逐次減一。想要找到擴充路徑,每種高度缺一不可。圖上各點不斷抬高。任何一種高度,一旦出現又消失,從此以後不會再有擴充路徑了,可以立即結束演算法。

時間複雜度O(V²E)。

UVa 10983

演算法:逐點送水版本
(Distance-directed Push-Relabel Algorithm)

引入Preflow Algorithm。Backtracking走訪容許圖。

Preflow Algorithm能夠優先找到每一點到匯點的阻塞流(水足夠時),形成局部的阻塞流!每次回溯皆實施relabel,隨時調校局部的最短路徑長度!

時間複雜度O(V²E)。

奧義

有了height的概念之後,我們可以重新審視之前的擴充路徑演算法,給予更簡潔的解釋。

Ford–Fulkerson Algorithm
Augmenting Path Algorithm
不使用height。
隨便找擴充路徑。

Edmonds–Karp Algorithm
Shortest Augmenting Path Algorithm
每回合都用BFS重新建立height,
同時用BFS找一條擴充路徑。

Dinitz' Algorithm
Blocking Flow Algorithm
每回合都用BFS重新建立height,
每回合都用多次DFS找擴充路徑(最後形成阻塞流)。

Ahuja–Orlin Algorithm
Distance-directed Augmenting Path Algorithm
一開始用BFS建立height(也可以全部設定為零),
每回合都用DFS找擴充路徑。

Maximum s-t Flow: Gabow's Algorithm (Capacity Scaling Algorithm)

演算法

容量視作二進位數字,從最高數量級開始,每回合添加一個位數,並且擴充流量。

重複以下步驟logC回合:
1. 每條邊容量翻倍:流量隨著翻倍。
2. 每條邊容量加零或加一。
3. 填滿多出的容量,達到最大流。

時間複雜度

一、總共logC回合。C是最大的管線容量。

二、每回合開始之前,源點到匯點的剩餘容量已經填滿。每回合開始之時,添加到圖上各條邊的容量只有0或1,剩餘容量頂多增加E,流量頂多擴充E。換句話說,每回合至多E條擴充路徑,就能達到最大流。

二甲、援引Shortest Augmenting Path Algorithm,找O(E)條擴充路徑達到最大流,時間複雜度O(E(V+E)),通常簡單寫成O(E²)。

二乙、或者援引Blocking Flow Algorithm,找O(V)次阻塞流達到最大流,整個過程至多E條擴充路徑,時間複雜度降為O(VE)。

時間複雜度O(VElogC)。

奧義

最大流問題只有四個要素:
 甲、容量(Capacity Graph)。甲≥0。
 乙、流量(s-t Flow)。甲≥乙≥0。
 丙、剩餘容量(Residual Graph)。甲減乙、反向乙。
 丁、遵行方向(Admissible Graph)。丁屬於丙:邊兩端高度差為一。

最大流問題:
 給定甲暨源點匯點,令乙趨近甲,求乙。

最大流演算法:
 以丙的視角看問題,有隙就流。(最大流最小割定理)
 以丁的視角看問題,可以縮短流動路線,加速演算法。

最大流演算法有兩大類:
 一、擴充路徑(率先流到匯點)
 Ford–Fulkerson Algorithm         丙上隨便找一條擴充路徑,不斷找。
 Augmenting Path Algorithm        O(EF)

 Edmonds–Karp Algorithm           丙上BFS找一條擴充路徑,最多VE次。
 Shortest AP Algorithm            O(VEE)

 Dinitz' Algorithm                丁上多次DFS找擴充流,最多V-1次。
 Blocking Flow Algorithm          O(VVE)

 Ahuja–Orlin Algorithm            丁上DFS找擴充路徑,最多VE次。
 Distance-directed AP Algorithm   O(VVE)

 Gabow's Algorithm                限制甲尺度找擴充流,最多logC次。
 Capacity Scaling Algorithm       O(VElogC)

 二、預流(率先流離源點)
 Preflow Algorithm                          回溯推  O(VVV)
 Push–Relabel Algorithm                     隨性推  O(VVE)
 FIFO Push–Relabel Algorithm                FIFO推  O(VVV)
 Highest-Label Push–Relabel Algorithm       最高推  O(VVsqrtE)
 Distance-directed Push–Relabel Algorithm   回溯推  O(VVE)