Flow

Flow Network

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

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

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

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

Flow(Network Flow)

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

Flow中譯為「流」。一個流便是由源點經管線至匯點的水流。一個流的權重(總流量),即是源點灌入的水流流量,同時也是匯點泄出的水流流量。

Maximum Flow(Max-Flow)

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

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

Minimum Flow(Min-Flow)

一滴水都不流,管線裡都沒水,就是Min-Flow,權重為零。大家應該都懂,所以就討論到這裡了。

圖例:不屬於流的玩意

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

圖例:合流、分流、交流

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

圖例:產生迴圈的流

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

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

感情很好的兩個點,一般視作內地裡波濤洶湧,流量無限大。

多重的邊變成單獨的邊

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

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

點的權重變成邊的權重

先前提到大家一般不考慮點的權重,其實是因為點的權重可以轉化為邊的權重。把原先有權重的P點改成兩個點Pin和Pout,原先連到P點的邊變成連到Pin,由P點連出的邊變成由Pout連出,P點的容量則由一條Pin到Pout的邊來取代之。

因此,在Flow的問題當中,點的權重可以改為邊的權重,最後只需要考慮邊的權重就行了。只考慮邊的權重,事情也簡單多了。

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

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

因此,在Flow的問題當中,多個源點和多個匯點可以改為一個源點和一個匯點,最後只討論一個源點和一個匯點就可以了。事情也變簡單多了。

無向邊變成有向邊

無向邊允許挑選流動方向,兩個方向都有相同的容量上限與容量下限,可以改為兩條方向相反的有向邊。但要注意一點是:這兩條方向相反的有向邊,只有其中一條可以用於流動。

因此,在Flow的問題當中,一條無向邊可以改為兩條方向相反的有向邊,最後只討論有向邊就可以了。事情也變簡單多了。

Max-Flow Min-Cut Theorem

一條小水流流量的瓶頸

水流流動時要符合管線容量限制。一條由源點流至匯點的小水流,其流量的瓶頸,會是流動路徑當中,容量上限最小的一條邊。

附帶一提,由於水流不會滲漏、不會淤滯,所以一條由源點流至匯點的小水流,其流動路徑上任意一條邊的流量,都會等於小水流的水流流量。

水流總流量的瓶頸

水一定從源點流至匯點。現在把圖上的點,依地理位置劃分作兩區,一區鄰近源點,另一區鄰近匯點──由源點區流入到匯點區的水流總流量,一定會小於等於由源點區橫跨到匯點區的管線總容量。反方向亦同。

如此說來,由源點流至匯點的水流總流量,其總流量的瓶頸,會是所有分區方式裡面,由源點區橫跨到匯點區的管線總容量之中,管線總容量最小的一個分區方式。

附帶一提,由於水流不會滲漏、不會淤滯,所以一個從源點流至匯點的流,其任意一種分區方式裡面,由源點區流入到匯點區的總流量,減去由匯點區流回到源點區的總流量,會等於由源點流至匯點的水流總流量。

Max-Flow Min-Cut Theorem

【讀者若不懂Cut,請參考「Graph Theory: Cut」。】

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

水一定從源點流至匯點。現在在圖上取一個源點與匯點不同側的Cut,也就是把圖上的點,劃分作兩側,一側包含源點,一側包含匯點──由源點側流入到匯點側的水流總流量,一定會小於等於由源點側橫跨到匯點側的管線總容量。反方向亦同。

如此說來,由源點流至匯點的水流總流量,其總流量的瓶頸,會是所有的源點與匯點不同側的割裡面,由源點側橫跨到匯點側的管線總容量之中,管線總容量最小的一個割。

附帶一提,由於水流不會滲漏、不會淤滯,所以一個從源點流至匯點的流,其任意一種分區方式裡面,由源點側流入到匯點側的總流量,減去由匯點側流回到源點側的總流量,會等於由源點流至匯點的水流總流量。

最後整理一下:

在一張圖上面任意取一個源點與匯點不同側的割。
定義流過此割的流量:由源點側流入到匯點側的總流量,減去由匯點側流回到源點側的總流量。
定義橫跨此割的容量:由源點側橫跨到匯點側的總容量。

根據瓶頸的概念,流過此割的流量會小於等於橫跨此割的容量。
因此「最大流的流量」等於「管線容量的最小割」。

由於水流不會滲漏、不會淤滯,在一個流當中,任取一個割,流過此割的流量等於水流總流量。

Max-Flow: Ford-Fulkerson Algorithm
(Augmenting Path Algorithm)

Ford-Fulkerson Algorithm
(Augmenting Path Algorithm)

給定一張有源點和匯點的圖,找出其中一個Max-Flow。

想法

在一個裝水的塑膠袋底部戳個洞,水就會流出來。戳越多洞,水就流出的越多。這意味著水一旦有隙可乘,就一定會源源而來、滔滔而至。要找最大流,其實與這個道理相同,讓水流不停地鑽空隙流至匯點,當無法再找到空隙時,就是極限了,就是最大流了。

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

溯洄沖減

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

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

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

Residual Capacity

水流要遵守管線容量限制。每一條涓流也都要遵守管線容量限制,其流量不得超過容量上限,只得就管線所剩下的空間來流動。residual capacity即是指管線剩下的空間,中譯「剩餘容量」。

一開始所有管線都是空的、沒有流量,管線的剩餘容量即等於管線容量上限:

令邊ij是一條由i點到j點的邊。令邊ji是一條由j點到i的邊。
flow[i][j] = 0;
flow[j][i] = 0;
residue[i][j] = capacity[i][j];
residue[j][i] = capacity[j][i];

當一條涓流流過管線後,就會變成:

如果有一條涓流流經邊ij。
flow[i][j] += 流量;
residue[i][j] = capacity[i][j] – flow[i][j];
residue[j][i] = capacity[j][i];

另外也要考慮溯洄沖減的涓流:

如果有一條涓流流經邊ij,然後之後又有一條涓流流經邊ji。
flow[i][j] += 流量1;
flow[j][i] += 流量2;
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。
flow[i][j] += 流量;
flow[j][i] = -flow[i][j];

如此一來,剩餘容量則可以直接以同一條管線的容量上限和流量相減而得:

residue[i][j] = capacity[i][j] – flow[i][j];
residue[j][i] = capacity[j][i] – flow[j][i];

這種方式下,一條管線絕對只有一個方向是正流量,另一個方向則是虛設的負流量。

各位可以思考一下剛剛介紹的這些方式,是否能用在有向圖和無向圖。

Augmenting Path

中譯「擴充路徑」。把握目前管線所剩下的空間,以及利用溯洄沖減方式,流出一條由源點至匯點的小小涓流,就是一條augmenting path,就是一條增加總流量的路徑,其流量可多可少(一般來說流量越多越好,能較快達到最大流)。只要一直找到augmenting path,總流量就會逐漸增加。

換個角度想,augmenting path就是在一張剩餘容量的圖上,任意一條由源點到匯點的路徑。只要一直找到augmenting path,剩餘容量就會逐漸減少,總流量就會逐漸增加。

每次流出一條涓流後,涓流中所有的邊,都會開放給之後的涓流進行溯洄沖減──也可以想做是剩餘容量圖上多了很多逆向管線,逆向管線的剩餘容量,等於涓流流過的流量。augmenting path可以經過這些逆向管線,來改善各條涓流的路線,妥善地利用剩餘容量,努力地增加總流量。

augmenting path的概念可以用於許多地方。這裡列出一題相關問題,供各位練習。

UVa 10806

正確性證明:利用水流總流量瓶頸(利用Max-Flow Min-Cut Theorem)

一張圖還找得到augmenting path的話,表示目前不是最大流,因為總流量得以藉由augmenting path而增加。

一張圖找不到augmenting path的話,表示這張圖中間有些管線已經沒有剩餘容量、已經滿溢(或根本沒有管線),造成水流無法由源點區流至匯點區,才會找不到augmenting path。

管線滿溢,等同於遇到了瓶頸,所以目前的流就是一個最大流。由源點開始,尚可流及的點集合(瓶頸之前),和無法流及的點集合(瓶頸之後),就是一個源點與匯點不同側的最小割。

另外值得順便一提的是,在一個最大流中,能找到的最小割不只一種。一般來說,要找最小割,可以先找源點側,也可以先找匯點側(邊的方向要反過來看),不過還是會有其他種類的最小割,這些最小割通常都很難被發現。

UVa 10480

演算法

不斷的找augmenting path,直到找不到為止。所有augmenting path總合起來便是Max-Flow,所有augmenting path的成本總和就是Max-Flow的權重。

augmenting path要怎麼找都可以,不一樣的augmenting path會產生不一樣的Max-Flow。下個章節會說明一種不錯的尋找方式。

時間複雜度

一個最糟糕的情況是:不斷找到流量超級少的augmenting path,時間複雜度是O(E*|f|),其中E是圖上的邊數,f是最大流的權重。

尋找一個最大流+計算最大流的權重(adjacency matrix)

Flow Decomposition

一個流有兩種拆解方式,或說是兩種數法:一、以圖上每一條邊的水流來看。二、以一條一條的augmenting path的水流來看。Ford-Fulkerson Algorithm使用後者來數最大流。

Max-Flow: Edmonds-Karp Algorithm
(Shortest Augmenting Path Algorithm)

Edmond-Karp Algorithm
(Shortest Augmenting Path Algorithm)

給定一張有源點和匯點的圖,找出其中一個Max-Flow。

Edmond-Karp Algorithm是Ford-Fulkerson Algorithm的加強版:每次找擴充路徑的時候,採用BFS,尋找由源點到匯點的最短路徑(想像管線長度皆為1),而且流量越大越好(到達瓶頸容量)。儘量避免浪費管線空間,也避免反覆地溯洄沖消,可以較快找到最大流。

最短路徑作為擴充路徑的好處

一、以點的觀點來看:在剩餘容量圖上,由源點到圖上每個點的最短路徑長度會逐步增加、或保持不變,但絕對不會減少。更進一步來說,每次找到的最短擴充路徑會逐漸變長,呈單調遞增成長。

此處稍做說明。回想Dijkstra's Algorithm所提到的greedy概念:一條最短路徑是由更短的最短路徑所組成。也就是說,由源點到擴充路徑上各個點所形成的路徑們,全部都是最短路徑。

擴充路徑被水流流過後,路徑上有些邊仍會有剩餘容量,仍存在於剩餘容量圖上;有些邊則一點不剩,從剩餘容量圖上消失了。綜合前文所述,這意味著由源點到擴充路徑上某些點的最短路徑已經沒啦。最短的路徑沒有了,所以最短路徑長度必會增加、或不變(當還有另一條一樣長的最短路徑的時候)。

最後再詳加考慮擴充路徑被水流流過之後,剩餘容量圖上增加的逆向邊。多出的這些逆向邊亦不會減少最短路徑的長度。

至此,可以確定以最短路徑作為擴充路徑,其路徑長度與日俱增、不會減少。

二、以邊的觀點來看:在流網路圖上,一條邊成為擴充路徑的瓶頸的次數會低於V/2次。更進一步來說,一張圖上最多只有O(V/2 * E) = O(VE)條擴充路徑。

【待補文字】

時間複雜度

時間複雜度等同於以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^2 * E)。

找出一個最大流+計算最大流的權重(adjacency matrix)

下面這個是別人寫的程式碼,相當精簡,可以參考看看:http://shygypsy.com/tools/

利用找出的最大流,從中找出一個最小割(adjacency matrix)

找出一個最大流+計算最大流的權重(adjacency lists)

UVa 820 10330 10779 563 10511

Max-Flow: Capacity Scaling Algorithm

Capacity Scaling Algorithm

給定一張有源點和匯點的圖,找出其中一個Max-Flow。

大意是:將容量數值記錄下來,然後設定為零。接著把原本的容量數值,由最高位bit到最低位bit,逐一添加到容量數值的尾端。每添加一個bit就找一次最大流,並持續累計計算的結果。

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

時間複雜度

一、找一條擴充路徑為一次Graph Traversal的時間,使用adjacency matrix為O(V^2),使用adjacency lists為O(V+E)。這裡採用adjacency lists的O(V+E),並省略V變成O(E)。

二、每個步驟中,先前的瓶頸的剩餘容量已經被填滿,而添加到圖上各條邊的容量只有0或1,先前的瓶頸的容量最多只增加1,整張圖來看由源點到匯點的容量最多只增加E。因此,每個步驟最多只會有O(E)條流量為1的擴充路徑,然後就達到當下的最大流了。細節請讀者自行探索。

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

根據上述三點,整個演算法的時間複雜度是O(E^2 * logC)。當C不大,會比Edmonds-Karp Algorithm快,尤其是Edmonds-Karp Algorithm每次所找到的擴充路徑的流量都很小的時候。

計算最大流的權重(adjacency matrix)

Max-Flow: Preflow-Push-Relabel Algorithm

Preflow-Push-Relabel Algorithm

給定一張有源點和匯點的圖,找出其中一個Max-Flow。

此演算法會運用到Ford-Fulkerson Algorithm提及的一些概念。讀者在繼續閱讀之前,請先預備知識。

壹、push

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

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

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

貳、excess和overflowing

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

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

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

參、residual capacity

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

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

肆、admissible edge

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

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

伍、height

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

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

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

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

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

陸、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:總共一次,是O(V)。

relabel:設定匯點的高度為0,源點的高度為V-1。最差的情況下,除源點和匯點外,最高的點升到了2V-3、最低的點升到了V,流不到匯點的水都回歸匯點了,如下圖所示。利用等差級數梯形公式計算一下,可以知道relabel最多會有O(V^2)次。一次relabel的時間是O(V),所以全部的relabel的時間是O(V^2 * V) = O(V^3)。

push:當一個含水點用relabel抬高之後,最差的情況是,此點位於高處,水沿著圖上各條邊,朝著低處流──意即每次relabel之後,可能會緊接著最多O(E)次push。整個演算法最多有O(V^2)次relabel,故最多有O(V^2 * E)次push。一次push的時間是O(1),所以全部的push的時間是O(V^2 * E * 1) = O(V^2 * E)。

歸納此三項,整個演算法需時O(V^2 * E),受限於push的時間複雜度。

找出一個最大流+計算最大流的權重(adjacency matix)

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

總結

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

Ford-Fulkerson Algorithm(Augmenting Path Algorithm) v.s. Preflow-Push-Relabel Algorithm

前者推水採取深度優先,率先流到匯點;後者推水則採取廣度優先(有設定高低次序)、隨機亂推(沒有設定高低次序),率先流離源點。兩者的解題概念其實都是在嘗試推水,只是推動次序不同罷了。

Max-Flow: Preflow-Push-Relabel Algorithm再進化

百尺竿頭,更進一步

我們可以加速此演算法!

順著由高到低的順序(或者更精確點,順著admissible network之拓樸順序),慢慢推動各點的水,不要每次都一口氣推水到最低處。如此便可以避免前面章節提到的情形:「push:當一個含水點用relabel抬高之後,最差的情況是,此點位於高處,水沿著圖上各條邊,朝著低處流──意即每次relabel之後,可能會緊接著最多O(E)次push。」

不必每次都一口氣推水到最低處,可以留待以後累積足夠水量再行推水。

讀者由前面章節一路讀來,應可了解順著高低順序推水是我們的初衷,這也絕對比沒秩序亂推水還要來的省時間。為了迫使各個含水點順著整體形勢推動水,在此先設計一個「discharge」的動作。

Discharge

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

演算法

1. Preflow
2. 不斷找符合條件的含水點實施discharge,
   直到所有含水點(除源點匯點)都沒水為止。
   條件:其他含水點(除源點匯點)的水,
   無法沿著目前的admissible network流入此含水點。

如果順著admissible network之拓樸順序,對各個含水點實施discharge,那麼每次relabel之後,僅需要O(V)次push。呼應本章開頭所言,整個演算法將由O(V^2 * E)變成O(V^3)。

要小心的是,當一個點進行relabel之後,會改變整張圖的admissible network,此時要謹慎選擇符合條件的含水點實施discharge。

時間複雜度

我們針對preflow、push、relabel的次數下手。preflow和relabel的時間複雜度都與先前章節相同。以下為push的時間複雜度分析:

甲、當所有點高度固定的情況下,對一個進行discharge的含水點來說,該演算法保證只會有水流出此點,並且不會有水流入此點。一個點最多擁有V-1個鄰點,故最多只會有 V-1次push。乙、一個點的高度範圍至廣為0到2V-3。丙、以上皆作用於圖上V-2個點,除去源點匯點。

由甲乙丙的乘積,可知全部的push的時間複雜度為O(V^3)。整個演算法的時間複雜度成為O(V^3)。

實作:一直找最高的含水點discharge

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
(Goldberg-Tarjan Algorithm)

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

演算法還可以再加速嗎?

當然是可以的!事實上均攤來看,一個點每次relabel之後,僅需要一兩次push就可以再relabel,然而我們的程式碼總是檢查所有的鄰邊,判斷能不能push,使得每次discharge都得花O(V)時間,而不是O(1)時間。如果我們能利用特殊的資料結構,一定可以再將演算法加速的!這就留給各位讀者去探討吧!

至於加速的極限呢?

push的次數:當一個含水點用relabel抬高之後,就得對此點進行push把水推到最低的鄰點,否則此點就無法再relabel。所以每次relabel之後最少都會有一次push,無法省略,所以push再怎麼少也有O(V^2)次。這比原先的O(V^3)次還少!另外我們還可以嘗試減少relabel次數,說不定push的次數可以少於O(V^2)次!

relabel的次數:若能避免兩個點之間反覆抬高、相互推水,而能一次抬高到定位,很有機會減少relabel的次數!

一次relabel所需的時間:目前需要以O(V)時間掃描所有鄰點,以找到最低的鄰點。如果以特殊的資料結構,更準確的知道哪個鄰點最低,就有可能加速!

Min-Cost Flow

Min-Cost Flow(Minimum Cost Maximum Flow)

中譯「最小成本流」、「最小費用流」。一張圖(流網路)上的每一條管線,除了有容量限制以外,還擁有單位成本──可以為正值,也可以為負值或零。現在水流流過管線時,每單位流量都會花費成本:

水流流過一條管線的成本,等於該條管線其流量與單位成本的乘積;一條小小涓流的成本,等於累加水流路徑上每一條邊其流量與單位成本的乘積;一個流的成本,等於累加圖上每一條邊其流量與單位成本的乘積。最小成本流就是指成本最小的最大流,可能會有許多個。

【註:cost在台灣譯作「成本」,詞意不太符合原意。在本章節中,讀者不妨把cost想做是「費用」(費用是對岸的譯法),水流流過管線時需要額外付出費用,儘可能的減少開銷──個人覺得此譯法比較貼近原意。】

Min-Cost Flow: Successive Shortest Path Algorithm

Successive Shortest Path Algorithm

閱讀此章節之前,讀者得先了解最短路徑。可參考本站文件「Graph──Shortest Path」。

給定一張有源點和匯點的圖,找出其中一個最小成本流。限制:圖上不得有負成本環。

想法

在Ford-Fulkerson Algorithm裡頭提到:不管擴充路徑怎麼找,一定都可以達到最大流。因此,在最小成本流當中,我們只需想辦法儘量降低每一次的擴充路徑的成本,不必考慮擴充路徑的流動路線和流量大小。【待補證明】

一開始沒有負成本環,以後就沒有負成本環。

只要一開始的圖沒有負成本環,之後不管怎麼找成本最小的擴充路徑,並在剩餘容量圖上增加逆向的邊(逆向時成本也隨之變號,也就是說多了很多負成本邊),剩餘容量圖上一定仍舊沒有負成本環。

如此一來,就可以確保可以從剩餘容量圖上,一直找到源點到匯點的最短路徑。

演算法

每次都尋找一條成本最小的擴充路徑,直到找不到為止。由於溯洄沖銷後,剩餘容量圖上會多出許多負成本邊,所以要找成本最小的擴充路徑,得利用各種可處理負邊的最短路徑演算法,例如Bellman-Ford Algorithm和Floyd-Warshall Algorithm和Johnson's Algorithm。

因為剩餘容量圖上沒有負環的原故,才能用最短路徑演算法找出一條由源點到匯點的簡單路徑,做為擴充路徑;如果剩餘容量圖上有負環,最短路徑演算法找出來的就不一定是一條簡單路徑,而有可能是包含了環的路徑。一條有環的路徑,會算不出這條擴充路徑的瓶頸流量。

找出一個最小成本流+權重+成本(adjacency matrix)

先提供一個比較差的實作方法。

找出一個最小成本流+權重+成本(adjacency matrix)

可以利用Dijkstra's Algorithm以及reweighting的手段,加快演算法速度。細節就省略了,直接給程式碼。(關於reweighting可參考最短路徑的Johnson's Algorithm章節)

UVa 10594

Max-Flow: Primal-Dual Algorithm

Primal-Dual Algorithm

給定一張有源點和匯點的圖,找出其中一個最小成本流。可以說是Successive Shortest Path Algorithm的加強版。

演算法

在Successive Shortest Path Algorithm當中,每次只找一條成本最小的擴充路徑。Primal-Dual Algorithm則是改良了前者,每次找出多條成本相等且最小的擴充路徑:

利用最短路徑長度,調整圖上所有邊的權重成為非負數之後,此時最短路徑上的邊必定會是零成本邊,而零成本邊都可能會成為最短路徑上的邊。要找出多條成本相等且最小的擴充路徑,就把圖上所有的零成本邊都找出來,然後在這些零成本邊所構成的圖當中,找最大流,便可以一次找到多條成本最小的擴充路徑。

找出一個最小成本流+權重+成本(adjacency matrix)

【待補程式碼】

Min-Cost Flow: Cycle Canceling Algorithm

Cycle Canceling Algorithm

給定一張有源點和匯點的圖,找出其中一個最小成本流。

在一個最大流當中,建立一條封閉的迴流,不會影響總流量,也不會違反流動的規則。只要找到一條成本為負的封閉迴流,就可以減少最大流的成本,而不會改變最大流的流量。

演算法

先嘗試找出一個最大流。然後不斷找負環,降低最大流的成本,直到找不到負環、無法降低成本為止,此時就是最小成本流。尋找負環可以使用各種可偵測負環的演算法,例如Bellman-Ford Algorithm和Label Correcting Algorithm。要找負環甚至也可以使用Minimum Mean Cycle,可加快演算法速度。

找出一個最小成本流+權重+成本(adjacency matrix)

【待補程式碼】

Circulation

Circulation

尚未有中文翻譯,暫譯為「循環流」、「封閉流」。循環流是一個沒有源點和匯點的流,水流不斷在流網路中循環地流動,遵守所有流動的規範。一個循環流的權重(總流量),是在流網路中流動的水流流量。

Augmenting Cycle

「擴充環」。藉由剩餘容量來增加整體流量的環狀水流,其概念與Augmenting Path相同。

Flow Decomposition

循環流可以拆成很多個Augmenting Cycle。這個道理就跟源點匯點流可以拆成很多條Augmenting Path是一樣的道理。

從一個循環流拆解Augmenting Cycle的時候,最差的情況是拆出一只環的時候,僅抹除掉一條邊的流量。圖上共有E條邊,所以一個循環流最多可以拆出E個不一樣的環。

拆解完之後,便可以知道循環流的權重(總流量)。

Max-Circulation(Maximum Circulation)

權重(總流量)最大的循環流,可能有許多個。尋找最大循環流的演算法:不斷找Augmenting Cycle,直到找不到為止。

Min-Cost Circulation(Minimum Cost Maximum Circulation)

成本最小的最大循環流,可能有許多個。尋找最小成本循環流的演算法,類似於最小成本流的演算法:不斷找成本最小的Augmenting Cycle,直到找不到為止。

Flow的問題使用Circulation來解

由匯點到源點接上一條容量無限大、成本無限小的邊,所有的擴充環為了增加流量、減少成本,都會想盡辦法經過這條邊。流量的瓶頸,就會被原圖限制住,所以圖上加了邊後的最大循環流的流量,就會是原圖的最大流流量。

Circulation的問題使用Flow來解

有一種不太正確的說法是:在循環流的外部加一個獨立的源點和一個獨立的匯點。但目前我自己也還沒想到要怎麼轉換。