動機
當殘量網絡中不再存在增廣路徑時,殘量網絡方法給出一個最大流。在容量均為整數的情形下,任意選取增廣路徑的算法會在不超過容量總和這個數值上界的步數內終止。該上界相對於容量的二進制編碼位元數可能是指數級的。若每次選取一條最短殘量路徑,便可得到更強的保證,且與容量的大小無關。
該算法通常稱為 Edmonds–Karp 算法。它的進展度量並不是流值(當容量為實數時,流值每次可能只增加任意小的量),而是各頂點在殘量網絡中的廣度優先距離。
定義
定義 3.9.1
(有容量的網絡與殘量弧)
設 為有限有向圖,其源點 與匯點 互異,各邊容量非負。可行流及其流值的定義與配套的最大流單元相同。每條原圖邊在其殘量容量為正時,分別對應一條正向殘量弧和一條反向殘量弧。即使相反方向的兩條原圖邊產生了平行的殘量弧,也須保留各弧自身的標識。
定義 3.9.2
(最短增廣路徑、距離與關鍵弧)
從零流開始。在每一輪迭代中,在當前殘量網絡上執行廣度優先搜尋(BFS),並沿一條最短的 – 路徑按其正的瓶頸值進行增廣。當不存在這樣的路徑時停止。設 為流 的殘量網絡中從 到 的 BFS 距離,對不可達頂點取 。若某條弧的殘量容量等於路徑的瓶頸值,從而在增廣後變為零,則稱該弧對此次增廣而言是關鍵弧。
定理
定理 3.9.3
(殘量距離不會減小)
沿一條最短殘量 – 路徑增廣之後,從 出發到每個頂點的殘量距離都不小於其先前的值,其中 規定大於所有有限值。
定理 3.9.4
(多項式增廣次數上界)
最短增廣路徑算法執行 次增廣。若採用鄰接表,並且先刪去原圖中從 不可達的頂點,則對於邊集非空的情形,在單位成本的精確算術模型下,總時間為 。
證明思路或證明
證明
(殘量距離不會減小)
假設某次增廣之後有某個距離減小了。在距離減小的頂點中,取新距離最小的頂點 ,並設 為一條新最短路徑的最後一條弧。則 ,並且由 的選取可知 的距離沒有減小。若弧 在增廣之前已是殘量弧,則由舊的最短路徑不等式得
與假設矛盾。因此該弧是新出現的殘量弧,它是增廣所用路徑上某條弧 的反向弧。沿舊的最短路徑有 。由於 的距離沒有減小,故 ,再次產生矛盾。這同時也排除了原先不可達的頂點變為可達的可能。
證明
(每條弧只會成為線性多次關鍵弧)
固定一條帶標識的殘量弧 。若它是關鍵弧,則它被飽和並消失。在這條弧再次成為關鍵弧之前,某次後續增廣必須使用與之配對的反向弧 ,使 重新變為正。在後一次使用該反向弧時,最短路徑距離滿足 。距離從不減小,而在先前那次作為關鍵弧被使用時 。因此在這兩個事件之間, 至少增加了 。有限的 BFS 距離至多為 ,所以每條帶標識的殘量弧至多只能 次成為關鍵弧。每次增廣至少含有一條關鍵弧,而帶標識的殘量弧至多有 條,由此得到增廣次數的上界。
證明透視
關鍵弧不能很快再次出現
主要的一步是用 BFS 距離而不是流值來衡量進展。距離的單調性依賴一個觀察:沿最短路徑增廣只會產生沿該路徑向後指的反向弧,即從距離 指向距離 ,這樣的弧不會提供捷徑。關鍵弧的計數還加上第二個要素:當一條被飽和的弧 之後恢復時,它的反向弧 曾在一條最短路徑上被使用,所以當時 ;而在飽和之時 。由於 不會減小, 至少上升了二。有限距離至多為 ,所以一條弧至多成為關鍵弧 次。若沒有最短路徑的規則,這兩個關係都不可用,常見錯誤一節中的反例顯示,增廣次數此時可以依賴於容量。
證明
(算法的代價與終止證書)
在原圖中從 不可達的頂點,不可能透過殘量更新而變為可達:新產生的反向弧連接的是已經位於某條增廣路徑上的兩個頂點。只需一次性刪去這些頂點,耗時 。餘下的相關圖至多有 個頂點,因此一次 BFS 加一次增廣的成本為 。把它與 次增廣相結合,即得所述的時間上界。若 被刪去,則零流已經是最大流。
終止時不存在增廣路徑,由配套的最大流最小割定理的證明,可得到一個容量等於流值的割。因此所返回的流是最大流。該論證作為精確算術下的數學算法,適用於實數容量;二進制位元複雜度與數值容差則是另外的問題。
例題詳解
例題 3.9.5
(一條最短增廣路徑)
若殘量路徑 與 同時存在,則 BFS 會先選兩條邊的路徑,而不選三條邊的路徑。只有當兩條路徑的邊數相等時,它才可能選擇其中任一條;容量並不決定 BFS 距離。
例題 3.9.6
(一個關鍵瓶頸)
若一條殘量路徑上各弧的容量為 ,則其瓶頸值為 。沿該路徑增廣 個單位會使中間一條弧飽和,這條弧即成為關鍵弧。若其他弧的殘量容量也等於該最小值,則它們同樣是關鍵弧。
例題 3.9.7
(反向弧可能出現)
沿一條原圖邊 發送一個單位的流,若該邊原本沒有反向殘量,就會產生一個單位的反向殘量容量 。之後使用這條反向弧,相當於抵消原有流的一部分;它並不是一條新的原圖邊。
常見錯誤
常見錯誤
(「最短」指弧數最少,而非瓶頸值最大)
BFS 在度量路徑長度時忽略殘量容量的大小。一條含兩條弧、瓶頸值為 的路徑,比一條含三條弧、瓶頸值為 的路徑更短。因瓶頸值較大而選擇後者,並不是此處所分析的算法。
反例模式
任意的增廣路徑可能需要很多步
增廣次數的界不能去掉最短路徑這一規則。設 為正整數。取邊 、、、,容量均為 ,再取邊 ,容量為 。假設算法交替地沿 增廣,以及利用 的反向弧沿 增廣。每條這樣的路徑瓶頸值恰好為一:第一條是因為 ,第二條是因為第一次增廣之後反向弧 的殘量容量為一。每次增廣加一個單位,邊 交替地載有一個單位和零個單位,而四條外側的邊各被使用 次。經過 次增廣之後流值為 ,這是最大的,因為離開 的邊容量總和為 。步數隨 增長,對 的位元數而言是指數級的。廣度優先搜尋則選取 與 ,瓶頸值各為 ,只需兩次增廣。修正後的說法保留最短路徑的規則,這樣得到的界與 無關。
常見錯誤
(流值並不是進展的度量)
對於任意實數容量,流值的嚴格增加本身並不能限制增廣的次數。多項式時間的證明轉而追蹤關鍵弧與 BFS 距離。在應用反向弧論證時,必須依據原圖邊的標識來區分平行的殘量弧。
為甚麼距離不會減小
距離性質的證明比較增廣前後兩個殘量圖。仍保持為正的弧原本已存在;一條弧只有在與之配對的反向弧被增廣所用時才會出現。容量可以增大或減小而不改變圖中弧的有無,但 BFS 距離只取決於弧是否存在,而不取決於其數值容量。
若存在新的更短路徑,取新距離最小的距離減小頂點 。它在某條新最短路徑上的前驅 的新距離更小,因而不是距離減小的頂點。若該前驅弧先前已存在,則先沿舊最短路徑到達 、再經過該弧,會與 處假設的距離減小相矛盾。若該弧是新出現的,則增廣使用了從 到 的相反弧。由於增廣路徑是最短路徑,沿該路徑的這條邊,舊距離恰好上升 。於是兩個不等式迫使 的新距離至少比舊距離大 ,這與「減小」相反。
最短增廣路徑不含重複頂點:刪去含重複頂點的一段會得到更短的路徑。最短路徑的每個前綴也是到其終點的最短路徑,這就說明了沿其各弧的距離關係。當存在多條最短路徑時,BFS 的實作可以選擇其中任一條;證明並不要求特定的擇取次序。
例題 3.9.8
(殘量距離而非容量)
設 BFS 給出距離 、、,所選路徑為 。發送流量之後,可能出現一條反向殘量弧 。這條新弧由距離 指回距離 ;它本身並不會產生從 到 的更短路線。一般性的證明同時處理所有新的反向弧,而不只是這一條。
仔細計數關鍵弧
當一條帶標識的弧的殘量容量變為零時,只有在某次增廣使用了與之配對的反向殘量弧之後,它才能重新獲得容量。若原圖在兩個方向上各有一條邊,它們仍然是兩條不同的原圖邊,各自擁有自己配對的殘量弧。屬於另一條原圖邊的、從 到 的弧,並不自動是被飽和弧的配對反向弧。保持這些標識,可以避免把容量的增加歸因於錯誤的邊。
設在某次迭代中 是關鍵弧。沿該次迭代的最短路徑,舊距離滿足 。當其配對反向弧 之後被使用時,當時的最短路徑距離滿足 。距離的單調性說明 的後來距離不小於其先前距離。因此 的後來距離至少是其先前距離加 。若此後 再次成為關鍵弧,單調性保證這一增量得以保持。
增廣路徑上的頂點是可達的,其距離至多為 。因此,一條帶標識的弧的起點距離至多只能增加 次 ,此後該弧就不可能再成為關鍵弧。對每次增廣選取一條關鍵弧,即把每次增廣記在某條弧名下,而每條弧至多被記 次。一條路徑上可能有若干個並列的瓶頸,但任取其中一個來記帳就已足夠。
從路徑搜尋到總成本
在鄰接表形式的殘量表示中,每條原圖邊至多貢獻兩條帶標識的殘量弧。BFS 對每條當前可用的弧至多檢查一次,並透過前驅指標復原一條最短路徑。增廣過程更新該路徑上每條弧及其配對反向弧的容量。實作時必須一致地保存這些配對連結,使得抵消流量時修改的是正確的原圖邊。
若某頂點在原有向圖中從 不可達,則從原本可達的頂點集合到它沒有原圖邊。起初它在殘量圖中不可達。每次增廣只使用當前可達的頂點,因此它所產生的任何反向弧也只連接當前可達的頂點。由歸納法,被排除的頂點不會變為可達。刪去它們不會消除任何增廣路徑。若餘下集合含 個頂點,則除 外每個頂點至少由一條原圖邊到達,故 。
經此預處理後,每次 BFS 與路徑更新耗時 。乘以增廣次數再加上預處理時間,對非空邊集得到 。若不做預處理的改進,則直接得到較寬鬆的界 。這些界計算的是精確算術與圖運算的次數,而不是任意實數的二進制位元複雜度。
流值、終止性與證書
每次增廣都保持容量約束與流量守恆,因為它沿殘量方向加上瓶頸值,並在被反向的原圖邊上減去瓶頸值。其流值嚴格增加,但多項式時間的終止性證明並不依賴於存在一個最小的正增量。這正是該結構性論證在數學模型中適用於實數容量的原因,而基於單位增量的整數容量證明則帶有對容量的數值上界。
當 BFS 無法到達 時,從 可達的殘量頂點構成割的一側。離開該側的每條原圖邊都已飽和;進入該側的每條原圖邊上的流為零,否則其反向弧將成為離開該側的殘量弧。該割的容量等於流值。這一對對象是可檢驗的最優性證書,與增廣了多少次無關。
選擇最短路徑對於距離單調性的證明是必要的。任意的增廣路徑在終止時可能同樣有用且正確,但若不證明相同的距離關係,上述關鍵弧計數便不能應用於它們。該界也並不意味著瓶頸值最大的路徑就是最短的;BFS 所用的是殘量弧的條數。
總結
最短殘量路徑使 BFS 距離非減。在同一條帶標識的弧兩次飽和之間,必須使用其反向弧,從而迫使其起點距離上升。對由此得到的關鍵弧上界求和,即證明增廣次數為多項式,並結合割證書,得到一個最大流。
練習
快速檢查
(不論容量如何,對 BFS 來說,含兩條殘量弧的路徑與含三條殘量弧的路徑,哪一條更短?)
BFS 數的是弧的條數,而不是容量。
解答 · 答案
含兩條弧的路徑更短。
快速檢查
(增廣之後,關鍵弧的殘量容量會怎樣?)
把它的容量與瓶頸值比較。
解答 · 答案
它的殘量容量變為零,因此會從殘量網絡中消失,直到它的反向弧被使用而恢復容量。
快速檢查
(為甚麼每次增廣都至少有一條關鍵弧?)
看一看取得最小值的那條弧。
解答 · 答案
一條有限的非空路徑中,至少有一條弧的殘量容量等於該路徑上的正最小值,這條弧會被飽和。
快速檢查
(當不再存在增廣路徑時,用甚麼證明當前的流為最大流?)
考慮從 可達的頂點。
解答 · 答案
從源點可達的集合定義一個割,它的容量等於可行流的值。由弱對偶性,流是最大的,割是最小的。
練習 3.9.9
(在容量為 、、、、 的網絡上運行 Edmonds–Karp 算法。給出每次增廣時 的 BFS 距離,並證明最大流的值。)
核心
其餘各對頂點之間都沒有邊。
解答(3)
- 1
沿兩條含兩弧的路徑增廣
此時 的距離為 。瓶頸值分別為 與 ,所以這兩次增廣之後流值為 。殘量容量變為: 為 , 為 , 為 , 為 。
依據: 與 都含兩條弧,可以先取其中任何一條。
- 2
再次搜尋
關鍵一步
的距離升為 ,這與定理相符。路徑 的瓶頸值為 ,所以流值成為 。
依據: 從 出發唯一的殘量路線經過 與弧 。
- 3
證明最優性
此時 與 都已飽和,BFS 只能到達 。割 的容量為 ,等於流值,所以最大流的值為 。 的距離依次為 ,沒有減小。