Dinic 演算法（Dinic's algorithm）
/ DEE-nitz /
埃德蒙茲-卡普一次增廣一條最短路徑，這浪費了力氣：許多最短路徑常共享結構，本可一起推送。Dinic 演算法把它們批次處理。它以階段（phase）運作；在一個階段內，從 s 到 t 的最短路徑距離固定，它在距離被迫增長之前，一次沿所有該長度的路徑盡量推送。正是這種批次處理把界壓到埃德蒙茲-卡普之下。
每個階段有兩步。第一，用從 s 出發的 BFS 在殘餘網路中建層次圖：給每個頂點它的 BFS 距離（層級），只保留從第 i 層通往第 i + 1 層的邊。層次圖中每條 s-t 路徑長度相同。第二，在這個層次圖中找一個阻塞流（blocking flow）——一個在每條 s-t 層次路徑上至少使一條邊飽和的流，使當前長度的流再也推不動。阻塞流可用反覆的 DFS 高效求得：沿可行邊前進，並對死路「撤退」（刪除），故每階段總工作量為 O(V * E)。一個阻塞流之後，最短 s-t 距離嚴格增加，故至多 V 個階段，整體得 O(V^2 * E)。在單位容量圖上，分析收緊為 O(E * sqrt(V))，這恰是 Hopcroft-Karp 用於二分圖匹配的界。
Dinic 是競賽程式與許多函式庫中的主力最大流演算法：比更進階的推送-重標號（push-relabel）變體簡單，卻對大型輸入夠快，而它在單位容量上的 O(E * sqrt(V)) 表現使它非常適合匹配與不相交路徑問題。要帶走的兩個想法是層次圖（它禁止橫向與後向的步，強迫前進）與阻塞流（它在一次掃描中榨出當前距離的所有增益）。一個實務提醒：高效的阻塞流實作需要「當前弧」（current-arc）優化（跳過已知無用的邊）才能真正達到所述的界。
階段的概念：若目前最短 s-t 路徑長度為 3，BFS 把頂點標為 0,1,2,3,...，只保留層級遞增的邊。一連串 DFS 推送在每條 s-t 路徑上各使一條邊飽和，直到沒有長度為 3 的路徑存活（一個阻塞流）。接著 BFS 重建層級——最短距離此時至少為 4——下一階段開始。
每階段：一次 BFS 建層級，再用 DFS 求阻塞流。至多 V 個階段，因為每次 s-t 距離都嚴格增長。
若沒有當前弧優化，阻塞流這一步可能反覆重訪死路邊，超出每階段 O(V*E)。O(V^2*E) 的界假設了這個優化到位；在單位容量上它收緊為 O(E*sqrt(V))。