Dinic's Algorithm — Fast Max Flow via Blocking Flows

Why it matters

Dinic is fast max flow. Understanding shapes competitive programming + large graph analysis.

The architecture

Phase: BFS build level graph (assign level = shortest path distance from source).

Blocking flow: find any max flow in level graph.

Repeat until no augmenting path.

How it works end to end

Level graph: only edges going from level i to level i+1.

Blocking flow: DFS finds augmenting paths; skips dead-ends.

Number of phases: O(V).

Special cases: unit capacity O(E√V); bipartite matching O(E√V).