s-t Flow

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

Flow Network

把一張圖想成是水流管線圖。圖上的邊想成是水管:邊的權重想成是水管的容量上限(容量下限預設為零),有向邊僅允許單向流動,無向邊得同時雙向流動。圖上的點想成是水管的接合點,並附有控制水流流向與流量的機器:點的權重想成是接合處的容量上限(容量下限預設為零),但是大家一般都不考慮點的權重。

每一條管線的流量數值與容量上限數值,以一斜線區隔,標記於圖上各條邊,方便觀看。水流流動時必須遵守各條管線的容量限制,不得有逾越容量限制之情事。流量數值與容量上限數值一定是正值或零,不得為負值。

在這張水流管線圖當中,水流流速是穩定的、是源源不絕的,有變化的只有水流流向與流量。因此,水流流動時,只要關心各條管線的方向限制和容量限制就可以了。

當一張圖專門用於水流流動時,則可稱之為Flow Network,中譯為「流網路」。

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

s-t Flow

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

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

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

Maximum s-t Flow

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

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

Minimum s-t Flow

「最小流」。一滴水都不流,管線裡都沒水,就是Min-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,請參考本站文件「Cut」。】

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

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

水流流動時要符合管線容量限制。一個從源點流至匯點的流,「由源點側流入到匯點側的總流量」會小於等於「由源點側橫跨到匯點側的管線總容量」。反方向亦同。

也就是說,一個從源點流至匯點的流,其總流量的瓶頸,會出現在「由源點側橫跨到匯點側的管線總容量」最低的一種分區方式。也就是容量的Minimum s-t Cut。

Max-Flow Min-Cut Theorem

「最大流最小割定理」其實就是談瓶頸。「網路流量的最大s-t流」等於「管線容量的最小s-t割」,管線若還有空間,就儘量增加流量,直到遇到瓶頸,瓶頸會出現在容量的最小s-t割。

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

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

若只找最大流流量,則可以運用求最小s-t割的演算法,計算管線容量的最小s-t割的權重,此即等同於最大流流量。

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

用途

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

Flow Decomposition

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

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

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

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

溯洄沖減的時候,可以選擇水量多寡和路線位置,藉以調整成不同的流。

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

UVa 10806 10380

Residual Network

每次增加一條小小涓流,都要時時刻刻遵守各條管線的容量限制。管線要有剩餘空間,或者管線有溯洄沖減的機會,涓流才能流過管線。

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

如此一來,涓流要進行流動,其實只要參考剩餘網路,遵守各條管線的剩餘容量限制就可以了。

剩餘網路是一個高度抽象概念,為的是整合涓流流動的容量限制。實作程式碼時,可以直接建立一個剩餘網路的資料結構,隨時利用容量與剩餘容量來計算流量。

Augmenting Path

「擴充路徑」,剩餘網路上面一條由源點到匯點的路徑。換個角度想,把握管線的剩餘空間,把握溯洄沖減,找出一條由源點至匯點的小小涓流路徑,就是一條擴充路徑。

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

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

演算法

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

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

擴充路徑要怎麼找都可以,
不一樣的擴充路徑有機會產生不一樣的最大流。
還找得到擴充路徑:
表示目前不是最大流,因為藉由擴充路徑,還可以再增加總流量。

找不到擴充路徑:
表示源點往匯點方向的一些關鍵管線已經沒有剩餘容量。沒有剩餘容量可推導出:
甲、管線沒有剩下來的空間(或根本沒有管線),也就是遭遇瓶頸。
乙、不能溯洄沖減。
根據最大流最小割定理,遭遇瓶頸時即是最大流。
【註:這部分的證明有漏洞。沒有考慮到形成迴圈的涓流。】

這個演算法的絕妙之處,是導入了溯洄沖減的機制,藉以調整流動路徑;然後把溯洄沖減併入了容量限制的思維,創立剩餘網路、擴充路徑等抽象概念;最後返回到最大流最小割定理,間接證明了溯洄沖減無論在什麼情況下,都能調整好流動路徑,找出最大流──調校水流的本質,就是剩餘網路。

另外可以發現,在整個過程當中,所有管線的剩餘容量的總和是固定不變的──只是源點往匯點方向的剩餘容量越來越少,匯點往源點方向的剩餘容量越來越多。整個過程可以看作是在調整剩餘網路的勢力走向──每次以擴充路徑擴充流量後,正方向會減少對應的剩餘容量,逆方向會增加對應的剩餘容量,源點與匯點之間的勢力差距越來越大。

時間複雜度

找一條擴充路徑為一次Graph Traversal的時間。圖的資料結構使用adjacency matrix為O(V^2);圖的資料結構使用adjacency lists為O(V+E),這裡省略V寫成O(E)。

最差情況是,不斷找到流量超級少的擴充路徑,共找到F條,F是最大流的流量。因此總時間複雜度,依據資料結構的不同,分別為O(V^2 * F)與O(EF)。

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

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

每一條邊的容量是定值;至於流量與剩餘容量,則有三種不同的記錄方式。第一種記錄方式。先前提到,兩條方向相反的有向邊,可以只讓一條邊擁有水流,另一條邊則沒有水流。在此利用沒有水流的那條邊:兩點之間其中一個方向是正流量,是真正流動的方向;另一個方向則是虛設的負流量,用來增加剩餘容量以利溯洄沖減。

一開始還沒有水流的時候:
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);

真正的流量則是正流量:
true_flow(i, j) = max(flow(i, j), 0);
true_flow(j, i) = max(flow(j, i), 0);

剩餘容量以管線的容量上限和流量相減而得:
residue(i, j) = capacity(i, j) – flow(i, j);
residue(j, i) = capacity(j, i) – flow(j, i);

第二種記錄方式。只要有涓流經過了管線,就把涓流流量直接累加在管線流量。雖然這種記錄方式會讓流量違背容量限制,可是在剩餘容量正確的情況下,還是能找出最大流。

令邊ij是一條由i點到j點的邊。令邊ji是一條由j點到i的邊。

一開始還沒有水流的時候:
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) 保持不變;

真正的流量是把雙向流量等量減少後而得(去掉溯洄沖減的部分):
true_flow(i, j) = flow(i, j) - min(flow(i, j), flow(j, i));
true_flow(j, i) = flow(j, i) - min(flow(i, j), flow(j, i));

剩餘容量以管線的容量上限和雙向流量計算而得:
residue(i, j) = capacity(i, j) – (flow(i, j) - flow(j, i));
residue(j, i) = capacity(j, i) – (flow(j, i) - flow(i, j));

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

令邊ij是一條由i點到j點的邊。令邊ji是一條由j點到i的邊。

一開始還沒有水流的時候:
residue(i, j) = capacity(i, j);
residue(j, i) = capacity(j, i);

有一條涓流經過邊ij之後:
residue(i, j) -= 流量;
residue(j, i) += 流量;

有一條涓流經過邊ij,又有一條涓流溯洄沖減,經過邊ji之後:
residue(i, j) = residue(i, j) - 流量1 + 流量2;
residue(j, i) = residue(j, i) + 流量1 - 流量2;
最後可歸納得出,當一條涓流經過邊ij的時候:
residue(i, j) -= 流量;
residue(j, i) += 流量;

真正的流量以管線的容量上限和剩餘流量相減而得,而且是正流量:
true_flow(i, j) = max(capacity(i, j) – residue(i, j), 0);
true_flow(j, i) = max(capacity(j, i) – residue(j, i), 0);

第一種方式最直覺。第二種方式中庸。第三種方式最精簡,實作簡單,不過最後要計算最大流的時候會比較麻煩。

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

延伸閱讀:容量上限不是有理數的時候

擴充路徑永遠找不完。

【待補圖片】

Maximum s-t Flow: Shortest Augmenting Path Algorithm(Edmonds-Karp 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^2 * VE) = O(V^3 * E);圖的資料結構為adjacency lists的話,通常把BFS的時間複雜度O(V+E),省略了V而寫成簡單的O(E),所以總共是O(E * VE) = O(V * E^2)。

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

UVa 820 10330 10779 563 10511 10983

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

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

想法

Shortest Augmenting Path Algorithm的加強版,改為找到一樣長的最短擴充路徑們。

Admissible Network

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

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

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

容許網路就是剩餘網路的「最短路徑圖」。「最短路徑圖」尚未成為專有名詞,「Next-to-Shortest Path」稍有提及。

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

Blocking Flow

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

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

剩餘網路上面,以阻塞流擴充流量,就斷絕了所有一樣長的最短擴充路徑。前面章節提到,利用Vertex Labeling with Shortest Distance估計不出結果,此處卻是使用這個方式。

演算法:找出一個阻塞流

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

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

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

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

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

演算法

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

時間複雜度

每次找到一個阻塞流並擴充流量之後,容許網路上面,所有由源點到匯點的最短路徑都阻塞了;剩餘網路上面,源點到匯點的最短距離會增加(擴充流量而新增的反向邊,也不會減少源點到匯點的距離),下次的最短擴充路徑會更長。

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

找一個阻塞流需時O(VE),最多找O(V)次,故總時間複雜度為O(V^2 * E)。

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

UVa 10546

延伸閱讀:Dynamic Trees

使用「Link-Cut Tree」記錄容許網路,尋找阻塞流可以加速到O(ElogV),整個演算法可以加速到O(VElogV)。

延伸閱讀:MPM Algorithm

http://www.cs.cornell.edu/Courses/cs4820/2013sp/handouts/DinicMPM.pdf

在容許網路上,定義一個節點的容量是min(所有出邊總和, 所有入邊總和),容量最小的節點即是瓶頸。找阻塞流時,不斷找到擴充路徑經過瓶頸(切兩段,先往源點找、再往匯點找),使用Binary Heap找瓶頸為O(V^2 * logV);使用Fibonacci Heap找瓶頸為O(V^2)。找V次阻塞流為O(V^3)。

Maximum s-t Flow: Capacity Scaling Algorithm

演算法

大意是:把容量的數值,由最高位bit到最低位bit,逐一添加到暫存容量的數值尾端。每添加一個bit,就以暫存容量找一次最大流。過程中持續累計計算的結果。

1. 令 C 為容量上限。C' 為依序添加bit的容量上限,一開始設為零。
2. 由 C 的最高位bit開始,直到 C 的最低位bit為止,不斷重複下面動作:
	甲、把 C 的該bit添加到 C' 的尾端。
	乙、當前流量成為方才的兩倍。
	丙、尋找擴充路徑(或擴充流),填滿 C' 多出的容量,達到當下的最大流。

時間複雜度

甲、找一條擴充路徑為一次Graph Traversal的時間。圖的資料結構使用adjacency matrix為O(V^2);圖的資料結構使用adjacency lists為O(V+E),這裡省略V寫成O(E)。

乙、每個步驟開始之前,由源點到匯點的剩餘容量都已經填滿。在每個步驟當中,添加到圖上各條邊的容量只有0或1,由源點到匯點的剩餘容量頂多增加E。也就是說,每個步驟頂多出現E條流量為1的擴充路徑,頂多只能擴充E大小的流量,就會達到當下的最大流了。

丙、令一張圖的管線容量最大者為C,一一拿出bit,所以這個演算法就會有O(logC)個步驟,以2為底的log。

由甲乙丙乘積可知,總時間複雜度,依據資料結構的不同,分別為O(V^2 * E * logC)與O(E^2 * logC)。

當C不大,會比Shortest Augmenting Path Algorithm快,尤其是Shortest Augmenting Path Algorithm每次所找到的擴充路徑的流量都很小的時候。

計算最大流的流量(adjacency matrix)

延伸閱讀:Unit Capacity Network

可以發現每個步驟中,增加的容量會形成一個Unit Capacity Network。Unit Capacity Network的最大流有極快速的演算法,時間複雜度為O(min{V^(2/3)*E, E^(3/2)}),以此可進行加速。

Maximum s-t Flow: Preflow, Push, Relabel

壹、push

想像一下:於源點放入足夠水量,然後用力推擠源點,就像針筒注射、發射水槍一樣,讓源點的水一股作氣鑽過整個流網路,最後從匯點噴出水流。

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

然而電腦程式無法直接實現「一股作氣鑽過整個流網路」,電腦程式只能一個一個算、一步一步算,所以我們只好一個一個點慢慢推進:首先推進源點的水到其它中繼點,再繼續推進中繼點的水到其他中繼點,一個接著一個點慢慢地推進到匯點。

貳、excess和overflowing

為了實現「一個接著一個點慢慢地推進」的想法,便定義圖上每個點都可以儲存水,成了「含水點」,其儲存水量稱作「含水量」。水被推到點上,得以暫時儲存在點上,以後隨時可以繼續推進。

建立含水點、含水量的系統之後,推進順序也無所謂了,因為水一直存在、不會消失,就算推歪方向,也可以往回推,回復原始狀態。

以「含水點」、「含水量」,設計一套找出最大流的方法:
子、先將源點的含水量設定成無限大。
丑、推進源點的水到圖上其他點,慢慢推向匯點,推進順序可隨意。
寅、多餘的水量,會受限於管線容量瓶頸,而留在源點和中繼點上。
卯、最後能夠推進到匯點的水量,就是最大流的流量。

參、residual capacity

推進的同時也記錄管線流量,便可以知道水流流動的情形。管線流量與剩餘容量的概念請參考前面的Augmenting Path Algorithm章節。

推進一個點的水,甲、要注意點的含水量,乙、注意管線的剩餘容量,丙、盡量填滿管線,營造出針筒注射、發射水槍的效果。

肆、admissible edge

「一個接著一個點慢慢地推進到匯點」,要確保各點的水是確實地推向匯點、聚集在匯點,避免漫無目的來回推進,避免環狀推進、不斷繞圈圈。因此導入了「水往低處流」的想法。

以「水往低處流」來設計方法、解決問題:
子、推向匯點:源點高、匯點低、其他點排好適當的高低順序。
丑、由源點漫溢:源點是最高點。
寅、朝匯點聚集:匯點是最低點。
卯、避免繞圈圈:不能推水到一樣高的點。只能推水到更低的鄰點。

伍、height label

為了實現「水往低處流」的想法,便定義圖上每個點都有一個「高度值」,並排好高低順序,由高往低推進、由源點向匯點推進。

高低順序有兩種安排方式:甲、反轉所有邊之後,以匯點為起點的最短路徑長度,作為高度值。乙、以源點為起點的最短路徑長度,取負值(可再加常數變成正值),作為高度值。

採用甲有個好處,因為推進規則可以改成:推進一個點的水,只能到、也只需要到「比此點剛好低一層」的鄰點。如此可以讓推進規則變得單純、容易實作,也依舊保持著水往低處流的原則。

排好高低次序,以及改變推進規則後,會出現新麻煩:甲、匯點不是最低點。乙、源點的水可能會推不出去。丙、現在要是推歪方向,就不能往回推了。丁、朝向匯點的管線容量不足時,一個點將會水洩不通。必須尋找其他管線,才能流向匯點。

以下將一一解決這些問題。

陸、source and target

無論是哪一種高低順序安排方式,都不能保證源點最高、匯點最低。採用甲,可以把源點的高度另設為V-1,源點就一定比圖上其他點高;匯點的高度維持為零,匯點就一定比圖上其他點低。V是圖上的點數。

柒、preflow

源點的高度設為V-1,推進又只能到「比此點剛好低一層」的鄰點,這造成一開始的時候,可能無法推進源點的水到所有鄰點,或說源點的水可能無法流到所有鄰點。

為了解決這種狀況,一開始的時候,就預先推進源點的水到所有鄰點,稱作「預流」。

捌、relabel

另外又追加了「抬高」的想法:當一個含水點水洩不通,就稍微抬高它,讓水可以流過其他管線,到達其他鄰點;甚至可以抬高到往回流,矯正水流流向。

現在不必預先設定每個點的高低次序了,只需固定源點和匯點的高度,讓各個點抬高後總是比源點低、比匯點高即可。想要推動一個含水點的水,就抬高此點;抬高一個含水點,就可以推動此點的水。

以「水往低處流」和「抬高含水點」來設計方法、解決問題:
子、推向匯點:抬高一個點到比匯點還高,但不能抬高匯點。
丑、由源點漫溢:源點是最高點,高度設為V-1,並預流。
寅、朝匯點聚集:匯點是最低點,高度設為0。
卯、避免繞圈圈:不能推水到一樣高的點。只能推水到剛好低一層的鄰點。
辰、避免水洩不通:抬高一個點比鄰近的點還高,以紓解積水。
巳、矯正流向:抬高一個點比來源的點還高,以豆退嚕。

玖、saturating push

如果一個含水點有許多鄰點,就先抬高含水點稍高於最低的鄰點,並推水到最低的鄰點,並盡量令管線滿溢;如果還有剩水,就再抬高含水點稍高於次低的鄰點,並推水到次高的鄰點,依此類推。以匯點的角度來看,朝向匯點的各條管線會陸陸續續流過水流並且滿溢,最後就會得到最大流。各位可以觀察看看。

當一個含水點水洩不通,表示下游已經遭遇瓶頸、或說下游管線已經滿溢(甚至根本沒有管線)、或說沒有剩餘容量、或說無法再推更多水到匯點、或說有多餘的水流不到匯點。

當一個含水點水洩不通,就抬高含水點,讓水往回流,矯正流向,替多餘的水,尋求其他出路,流到匯點。相反的,當一個含水點河涸海乾時,就沒有必要抬高此點,找自己麻煩。

拾、retreat(沒有專用術語,故自行命名)

當水量過剩,又不斷抬高圖上每個點,最後圖上每個點都會比源點還高,所有剩水都會回歸源點。這剛好可以作為演算法的閉幕。此時圖上的水流流動情形就是最大流。

以「水往低處流」和「抬高含水點」來設計方法、解決問題:
子、推向匯點:抬高一個點到比匯點還高,但不能抬高匯點。
丑、回歸源點:抬高一個點到比源點還高,但不能抬高源點。
寅、由源點漫溢:源點是最高點,高度設為V-1。
卯、朝匯點聚集:匯點是最低點,高度設為0。
辰、避免繞圈圈:不能推水到一樣高的點。只能推水到剛好低一層的鄰點。
巳、避免水洩不通:抬高一個點比鄰近的點還高,以紓解積水。
午、矯正流向:抬高一個點比來源的點還高,以豆退嚕。

小結

欲讓水「一股作氣鑽過整個流網路」計算最大流,電腦卻只能「逐點推進」,只好製作一些中繼的「含水點」,加入「水往低處流」的概念,以匯點為起點的最短路徑長度設定「高低次序」,迫使水流向匯點。但是卻導致「源點不是最高點」、「源點無法推水」、「無法矯正流向」、「水洩不通」等諸多問題。於是又出現了「設定源點匯點高度」、「預流」、「抬高」的想法,解決了上述問題,從此亦不再需要安排「高低次序」。至於無法推到匯點的剩水,恰可藉由「抬高」而回歸源點,演算法完美結束。

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

Preflow

推動源點的水到所有鄰點。
(源點可以不必設定水量,不影響結果。)

Push

給定一個含水點和一個與其相鄰的點,推水過去。
以下是允許進行Push的條件,確定符合後才得進行Push:
壹、含水點不是源點和匯點。(源點已預流,匯點收集水。)
貳、含水點仍有水。
参、含水點到其鄰點的邊仍有剩餘容量。
肆、鄰點是比含水點低一層的點。

Relabel

給定一個含水點,抬高此含水點。
以下是允許進行Relabel的條件,確定符合後才得進行Relabel:
壹、含水點不是源點和匯點。(請參考Push,沒必要推動就沒必要抬高。)
貳、含水點仍有水。
参、含水點水洩不通。
  含水點藉由有剩餘容量的邊,所連到的鄰點,這些鄰點的高度都小於等於含水點。
  (當含水點仍找得到低一層的鄰點可以推水過去,就不能抬高。)

演算法

1. 把圖上每個點的高度設為零。
   (或者是以匯點作為起點的最短路徑長度作為高度,不影響結果。)
2. 設定起點的高度是V-1(以上),V為圖上點數。
3. preflow。
4. 圖上各點不斷push或relabel,次序隨意,直到無法進行為止。
   (或者說,直到圖上除源點匯點以外的所有點都沒水為止。)
5. 匯點所收集的水量,即是最大流的流量。
   多餘的水流回源點後,源點所流出的水量,即是最大流的流量。
   圖上每條邊的水流,總合起來就是最大流。

經由複雜的推導,總算歸納出單純的演算法──僅以三種「點對鄰點之間」的動作preflow、push、relabel,即可求得最大流。十分精采!

時間複雜度

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

preflow:總共一次,O(V)。

relabel:設定匯點的高度為0,源點的高度為V-1。最差的情況下,除源點匯點,最高的點升到了2V-3、最低的點升到了V,流不到匯點的水都回歸匯點了,如下圖所示。利用等差級數梯形公式,得知relabel總共最多O(V^2)次。

圖的資料結構為adjacency matrix,一次relabel需時O(V),全部的relabel需時O(V^2 * V) = O(V^3);圖的資料結構為adjacency lists,圖上各點各做一次relabel需時O(E),全部的relabel需時O(E * V) = O(VE)。

saturating push:對一條邊而言,兩個端點高度逐漸升高,高度範圍為0到2V-3,高度相差一時才能推動,一種高度頂多推動一次,所以一條邊的saturating push總共最多O(V)次。

圖的資料結構為adjacency lists,一次push需時O(1),一條邊的saturating push總共最多O(V)次,圖上總共E條邊,全部的saturating push需時O(VE)。

non-saturating push:同上,一種高度最多推動V次。由於其端點的V個鄰點升高時會補水給端點、其端點最多補水V次。全部的non-saturating push需時O(V^2 * E)。

歸納上述四項,整個演算法的時間複雜度為O(V^2 * E),受限於non-saturating push的次數。

計算最大流的流量(adjacency matix)

實作時我們建立一個queue來儲存含水點。

Maximum s-t Flow: Discharge

想法

順著高低順序推水是我們的初衷。累積足夠水量後,就慢慢往前推動,不要每次都一口氣推水到最低處,便可以減少push的次數。

Discharge

給定一個含水點,不斷使用Push和Relabel把水排掉,直到沒水。
以下是允許進行Discharge的條件,確定符合後才得進行Discharge:
壹、含水點不是源點和匯點。
貳、含水點仍有水。

演算法

1. preflow。
2. 不斷找符合條件的含水點實施discharge,
   直到所有含水點(除源點匯點)都沒水為止。

   條件:其他含水點(除源點匯點)的水,
   無法沿著目前的admissible network流入此含水點。

【待確認】

時間複雜度

我們針對preflow、push、relabel的次數下手。preflow、relabel、saturating push的時間複雜度都與先前章節相同。此處只分析non-saturating push的時間複雜度。

【待補文字】

由均攤分析可知non-saturating push總共O(V^3)次。整個演算法的時間複雜度為O(V^3)。

演算法:一直找最高的含水點discharge
(Highest-Label Preflow-Push Algorithm)

1. preflow。
2. 一直找最高的含水點進行discharge(不包括源點匯點),
   直到圖上無含水點(不包括源點匯點),

演算法:含水點discharge後,若有升高則挪動順序至首
(Relabel-to-front Algorithm)

1. 建立一個list,裡面包含所有點(但不包括源點匯點)。
   註:此list從頭到尾一直都是當下admissible network的拓撲排序。
2. preflow。
3. 按照list順序讀取各點
   甲、如果不是含水點,就繼續下一個點,
   乙、如果是含水點,就discharge,並且於discharge完之後
      a. 如果剛才的discharge有抬高此點(有relabel),
         就把此點移到list開頭,並重新由list開頭讀取。
      b. 如果剛才的discharge沒有抬高此點(沒有relabel),
         就繼續下一個點。

演算法:含水點以FIFO順序discharge
(FIFO Preflow-Push Algorithm)

1. 建立一個queue,裡面只放含水點(但不包括源點匯點),含水點不會重複。
2. preflow,順便把含水點都放入queue。
3. 不斷從queue中取出點進行discharge,直到queue中無點。
   若discharge時產生了queue裡面沒有的含水點,就放入queue。

Maximum s-t Flow: Improved Shortest Augmenting Path Algorithm

註記

此演算法沒有廣為人知的正式名稱。

此演算法為Ahuja與Orlin於1991年發表,論文名稱是Distance-directed augmenting path algorithms for maximum flow and parametric maximum flow problems。該篇論文中同時發表了兩個最大流演算法,因此若直接稱呼Distance-directed Augmenting Path Algorithm,會無法準確指出是哪一個演算法。

Ahuja與Orlin後來出版一本網路流的書籍,書上描述此演算法為「Shortest Augmenting Path Algorithm的改良版」,但是仍未給予一個適切的名稱。

演算法

Preflow-Push Algorithm的加強版。以DFS的順序沿著admissible edge行走,當遇到死胡同,就relabel,並且回溯,尋找其他可以到達匯點的路徑。

與Preflow-Push Algorithm不同的地方,在於此演算法是找到匯點之後,才沿著擴充路徑來擴充流量,而不是逐點推水。

時間複雜度仍是O(V^2 * E)。

尋找擴充路徑,沿著admissible edge行走,從源點走到匯點,途中各點的高度顯然是逐次減一。缺一不可。

任何一種高度出現了、又完全消失之後,表示源點到匯點往後無法貫通,開始retreat,可以直接結束演算法。此即cnt的功用。

UVa 10983

演算法

引入blocking flow的概念。以backtracking的順序而非DFS的順序沿著admissible edge行走,尋找擴充流而非擴充路徑。

特色是尋找每一點到匯點的阻塞流(水足夠時)、也就是尋找局部的阻塞流!每次回溯皆實施relabel,隨時調校局部的最短路徑長度!

時間複雜度O(V^2 * E)。

延伸閱讀:height label

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

Augmenting Path Algorithm(Ford-Fulkerson Algorithm)
不使用height label。
隨便找擴充路徑。

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

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

Improved Shortest Augmenting Path Algorithm
一開始用BFS建立height label(也可以全部設定為零),
每回合都用DFS找擴充路徑。

摘要

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

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

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

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

 Shortest Augmenting Path Algo.     丙上BFS找一條擴充路徑,最多VE次。
 (Edmonds-Karp Algorithm)           O(V*E*E)

 Blocking Flow Algorithm            丁上找擴充流,最多V次。
 (Dinic's Algorithm)                O(V*V*E)

 Improved Shortest Augmenting       丁上找擴充路徑,最多VE次。
 Path Algorithm                     O(V*V*E)

 Capacity Scaling Algorithm         限制甲尺度找擴充流,最多logC次。
                                    O(E*E*logC)

 二、預流推進法(率先流離源點)
 Preflow-Push Algorithm             隨性推  O(V*V*E)
 Relabel-to-front Algorithm         插隊推  O(V*V*V)
 FIFO Preflow-Push Algorithm        FIFO推  O(V*V*V)
 Highest-Label Preflow-Push Algo.   最高推  O(V*V*V)

Maximum s-t Flow: Orlin's Algorithm

http://jorlin.scripts.mit.edu/Max_flows_in_O(nm)_time.html

目前時間複雜度最低的演算法。使用一些糟糕的手法硬湊出來的,缺乏實務價值。