埃德蒙茲-卡普演算法（Edmonds-Karp algorithm）
/ ED-mundz KARP /
福特-富爾克森能用，卻留下一個危險的自由：用哪條增廣路徑。埃德蒙茲-卡普以一條有紀律的規則消除危險——總是選一條最短的增廣路徑，以邊數計。這單一選擇把一個速度取決於容量大小的方法，轉成一個有乾淨多項式保證、且不在乎容量多大的演算法。
埃德蒙茲-卡普就是用廣度優先搜尋在殘餘網路中找增廣路徑的福特-富爾克森，所以每條路徑在當前可用的 s-t 路徑中邊數最少。時間複雜度為 O(V * E^2)。它之所以是多項式，倚賴兩個可以平白陳述的事實。其一，隨著增廣進行，殘餘網路中從 s 到任一頂點的 BFS 距離絕不減少（單調不減）。其二，每條邊至多 O(V) 次成為某增廣路徑的瓶頸（飽和、殘餘最小的邊），因為兩次這種事件之間，到它某個端點的距離必嚴格增加，而距離以 V 為界。共有 E 條邊，故至多 O(V * E) 次增廣；每次 BFS 花 O(E)，整體得 O(V * E^2)——關鍵在於不依賴容量的大小。
埃德蒙茲-卡普是最大流可在強多項式時間內求解的第一個證明，且實作簡單：只要在增廣迴圈裡用 BFS 取代任意搜尋。實務上它快速可靠，不過 Dinic 演算法藉由一次沿許多條最短路徑增廣（每階段一個阻塞流）把界改進到 O(V^2 * E)。誠實的說法：埃德蒙茲-卡普與其說是新想法，不如說是有紀律的福特-富爾克森——BFS 規則正是馴服樸素方法最壞情況的關鍵。
在那個「中間邊容量為 1」的壞網路上，樸素福特-富爾克森可能要約 2000 次增廣，而埃德蒙茲-卡普的 BFS 先找到那兩條短的直接路徑（各 2 條邊），忽略穿過中間的較長曲折，無論那些容量 1000 的邊如何，都在 2 次增廣內完成。
選邊數最少的增廣路徑（BFS）就是全部訣竅——它把增廣次數限在 O(V*E)，與容量無關。
O(V*E^2) 的界與容量大小無關，修正了福特-富爾克森的最壞情況。但在稠密圖上它仍比 Dinic 的 O(V^2*E) 慢，且遠慢於像 Hopcroft-Karp 這類專門的二分圖匹配界。