貪婪的想法，以及它裂開的地方
上一篇導覽給了我們 流網路 中一個合法的 流：每條邊上一個數，永不超過容量，且除了源點 s 與匯點 t 之外，每個節點都滿足守恆。現在我們想要最大可能的 流值。第一直覺是純粹的貪婪：找任何一條從 s 到 t、每條邊都還有空間的路徑，沿最緊的那條邊能推多少就推多少，重複直到再無這樣的路徑為止。這很吸引人、很好想像，而且——就這樣原封不動地——是錯的。
經典的陷阱在這裡。看一個菱形：s -> a、s -> b、a -> t、b -> t 各容量 3，外加中間單一條邊 a -> b 容量 3。如果貪婪先沿 s -> a -> b -> t 送 3 個單位，每條中間與瓶頸邊都填滿了，於是再沒有任何 s 到 t 的路徑還有空間。貪婪回報流值為 3 然後停下。但真正的最大值是 6：沿 s -> a -> t 送 3、沿 s -> b -> t 送 3，完全不碰中間那條邊。那個早早做下的貪婪選擇在局部沒問題，全域卻是個大失誤——這正是貪婪那一輪 貪婪可能失敗 的教訓，現在在流的問題上咬了我們一口。
診斷很精確：一旦我們把一個單位的流委派給某條邊，樸素的貪婪便永遠無法重新考慮。要達到流值 6，我們必須「撤銷」坐在 a -> b 上的那 3 個單位——也就是說「其實，把那股流改走別處」。一個正確的演算法，需要一種辦法去送「新」的流，而當這樣做能釋放出更好的整體繞法時，同時也「抵銷」掉「舊」的流。那單一個需求——能夠往回推——正是殘餘網路存在的全部理由。
建構殘餘網路
殘餘網路，對當前流 f 寫作 G_f，是網路的一份記帳副本，它對每一個可能的動作，記錄此刻還能沿它走多少流。它有兩種邊，而第二種是聰明之處。對一條原始邊 u -> v、容量 c、載著流 x，殘餘網路保有一條 前向邊 u -> v，殘餘容量為 c - x（還空著的空間），「以及」一條 後向邊 v -> u，殘餘容量為 x（等於當前在那裡的流量）。
把那兩條邊唸出聲來。前向邊說：「這條管子還有 c - x 的餘裕，你可以加那麼多。」後向邊說：「已經有 x 個單位沿 u -> v 流動了；在相反方向 v -> u 送至多 x 個單位並不違反物理——它只是『抵銷』掉你已委派的一部分流。」沿後向殘餘邊推，並不是水往高處流；它是一個收回先前決定的記帳動作。那正是貪婪版本所缺的、那個失蹤的「撤銷」鍵。
沿殘餘路徑增廣
增廣路徑 就只是殘餘網路 G_f 中任何一條從 s 到 t 的路徑——可自由使用前向與後向殘餘邊。它的 瓶頸 是沿途最小的殘餘容量；叫它 b。我們藉由沿整條路徑推 b 個單位來增廣。對路徑的每一步，意義取決於邊的類型：一條前向殘餘邊 u -> v 表示在真實邊 u -> v 的流上「加」b；一條後向殘餘邊 v -> u 表示在真實邊 u -> v 的流上「減」b。無論哪種，b 至少為 1（在整數網路裡），所以流值嚴格增加。
為何結果仍是合法的流？在路徑上某個內部節點走一遍守恆檢查。路徑從一條殘餘邊進入該節點、從另一條離開，而在每一種組合裡——進前向／出前向、進後向／出前向，諸如此類——該節點處「流入減流出」的淨變化恰好是零。容量也維持被遵守：一次前向推 b 從不超過它被允許的殘餘 c - x，一次後向推 b 也從不移走多於原本在那裡的 x。所以增廣把一個合法的流，映成一個流值嚴格更大的合法的流。這就是 福特-富爾克森方法 的核心。
- 回到菱形，在貪婪卡在流值 3、有 3 個單位走 s -> a -> b -> t 之後。建出 G_f。邊 a -> b 滿了，所以它的前向殘餘消失，但一條容量 3 的後向殘餘邊 b -> a 現在出現了。
- 找一條增廣路徑：s -> b（前向，空間 3），接著 b -> a（「後向」，空間 3——這就是撤銷），再 a -> t（前向，空間 3）。瓶頸 b = 3。
- 推 3：在真實邊 s -> b 與 a -> t 上加 3，並在真實邊 a -> b 上減 3（把它抵銷回 0）。現在的流是 s -> a -> t 上 3、s -> b -> t 上 3。流值從 3 跳到 6——真正的最大值——純粹是靠讓某一步往回走。
我們何時停下，而它對嗎？
這方法的停止規則美妙地簡單：持續增廣，直到殘餘網路裡完全沒有 s 到 t 的路徑為止。深刻的回報是，這不只是「我們放棄了」——它是一張最佳性的證書。當不存在增廣路徑時，在 G_f 中仍從 s 可達的節點集，構成一個 s-t 割 的一側，而可以證明當前流的流值恰好等於那個割的容量。既然每個流的流值至多等於每個割的容量（弱對偶，承襲上一輪的精神），讓它們相等就證明了兩者皆為最佳。那個相等，就是 最大流最小割定理，下一篇導覽的主角——而增廣路徑正是我們真正用來證明它的工具。
終止需要小心，而這裡的誠實很重要。在整數容量下，每次增廣讓流值至少升 1，而流值被「離開 s 的總容量」由上界住，所以迴圈必在有限多步後停下——流值是一個不會永遠上升的良基測度。但通用的福特-富爾克森方法「不」保證步數很少：如果你隨便挑增廣路徑，你可能需要與最大流值本身成正比的增廣次數。在一個容量像 1000000 的圖上，對手能逼你以微小的增量一次一個單位地爬上去。
埃德蒙茲-卡普、迪尼茨，以及挑路徑換來什麼
第一個修法乾淨到幾乎令人不好意思。埃德蒙茲-卡普 就是福特-富爾克森加一條規則：總是挑邊數「最少」的增廣路徑——也就是一條 以邊數計的最短路徑，用殘餘網路裡一個樸素的 廣度優先搜尋 找到。憑這單一條紀律，可以證明增廣次數至多 O(V*E)，與容量值無關。每次廣度優先搜尋花 O(E)，所以整個演算法以 O(V*E^2) 執行。容量已從界裡徹底消失——上面那種病態的緩慢不見了，純粹因為廣度優先搜尋從不把增廣浪費在繞遠的路徑上。
為何「最短優先」管用？關鍵引理是：殘餘網路裡從 s 到 t 的廣度優先搜尋距離，在演算法執行過程中從不「減少」，而且嚴格增加得夠頻繁，使總增廣次數被界住。證明是仔細審視一條後向邊如何可能重新出現，而它是整個主題裡較漂亮的計數論證之一。你不需要把證明記在腦裡才能用這演算法，但值得知道這個加速是靠一個誠實的不變量掙來的，而非靠運氣。
迪尼茨演算法 把同樣的想法再往前推，也是你在實務上會去拿的工具。它不是一次一條最短路徑，而是每個階段先跑一次廣度優先搜尋算出 層次圖——把節點按與 s 的距離分層——再在那張分層圖裡找一個 阻塞流，在重跑廣度優先搜尋之前，一口氣飽和許多條最短路徑。這壓縮了每階段的工作量，一般得出 O(V^2 * E)，在單位容量網路上更進步到 O(E * sqrt(V))——正是這個界，讓兩篇之後以流為基礎的 二分圖匹配 真正地快。同樣的殘餘網路、同樣的增廣路徑原理；只有推流的排程變得更聰明。
依著整條階梯的精神，給一個收尾的提醒：那些界是最壞情況的漸進量，一般的 隱藏常數 但書都適用。在真實、有結構的輸入上，這三種方法往往遠比它們的保證更快結束，而一個「較慢」的界可能在某一族特定的圖上勝出。三個名字的重點不是一個嚴格排名，而是一份菜單：殘餘網路是那唯一一個想法，而你挑哪些增廣路徑——任意、最短、或一整層阻塞——是在實作工夫與可證的最壞情況之間做權衡。