Dinic's algorithm
/ DEE-nitz /
Edmonds-Karp augments one shortest path at a time, which wastes effort: many shortest paths often share structure and could be pushed together. Dinic's algorithm batches them. It works in phases; within a phase, the shortest-path distance from s to t is fixed, and it pushes as much as possible along all paths of that length at once before the distance is forced to grow. This batching is what lowers the bound below Edmonds-Karp.
Each phase has two steps. First, build the level graph by BFS from s in the residual graph: assign each vertex its BFS distance (its level) and keep only edges that go from level i to level i + 1. Every s-t path in the level graph has the same minimum length. Second, find a blocking flow in this level graph — a flow that saturates at least one edge on every s-t level path, so no more flow of the current length can be pushed. A blocking flow is found efficiently by repeated DFS that advances along admissible edges and 'retreats' (deletes) dead ends, so total work per phase is O(V * E). After a blocking flow, the shortest s-t distance strictly increases, so there are at most V phases, giving O(V^2 * E) overall. On unit-capacity graphs the analysis tightens to O(E * sqrt(V)), which is exactly the Hopcroft-Karp bound for bipartite matching.
Dinic is the workhorse maximum-flow algorithm in competitive programming and many libraries: simpler than the more advanced push-relabel variants, yet fast enough for large inputs, and its O(E * sqrt(V)) behavior on unit capacities makes it excellent for matching and disjoint-path problems. The two ideas to carry away are the level graph (which forbids sideways and backward steps, forcing progress) and the blocking flow (which extracts all gains of the current distance in one sweep). A practical note: an efficient blocking-flow implementation needs the 'current-arc' optimization (skip edges already known to be useless) to actually hit the stated bound.
Phase idea: if the shortest s-t path currently has length 3, BFS labels vertices 0,1,2,3,... and keeps only level-increasing edges. A series of DFS pushes saturates one edge per s-t path until no length-3 path survives (a blocking flow). Then BFS rebuilds levels — the shortest distance is now at least 4 — and the next phase begins.
Per phase: one BFS to build levels, then a blocking flow by DFS. At most V phases since the s-t distance strictly grows each time.
Without the current-arc optimization, the blocking-flow step can revisit dead-end edges repeatedly and blow past O(V*E) per phase. The O(V^2*E) bound assumes that optimization is in place; on unit capacities it sharpens to O(E*sqrt(V)).