The idea: one BFS, many augmenting paths

Edmonds-Karp runs a whole breadth-first search for every single augmenting path. Dinic's algorithm (Yefim Dinitz, 1970) runs one BFS and then pushes flow along all the shortest augmenting paths it found before searching again. The work is split into phases; each phase has two steps:

  1. BFS levels. A BFS from the source s in the residual graph gives every vertex a level: its distance in edges from s.
  2. Blocking flow. Depth-first searches push flow along paths that always go from one level to the next, until no such path is left.
The sample network with levels: s on level 0, a and b on level 1, c and d on level 2, t on level 3. Arcs from one level to the next are kept; the edges a to b and d to c stay inside a level and are left out.
The level graph of phase 1 keeps only arcs that go one level down; a→b and d→c stay inside a level and are ignored this phase.

Edge labels on the canvas are flow/capacity, so 4/10 means 4 units on an edge of capacity 10. The sample network is the one from the Wikipedia article on the algorithm, with the vertices renamed a to d.

Step 1: BFS levels and the level graph

The BFS uses every residual arc with room left: along an edge u → v the room is c − f, and against it (a back arc v → u) the room is f, the flow that can be cancelled. The level graph keeps an arc u → v only when level(v) = level(u) + 1. Every path from s to t in it is a shortest augmenting path, with exactly dist(s, t) edges. On the canvas, kept arcs are blue (along the edge) or magenta (a back arc); the rest are faded.

Step 2: a blocking flow with current arcs

A blocking flow is a flow in the level graph after which every s–t path of the level graph has at least one full arc. It is not necessarily a maximum flow of the level graph; it just leaves no path open. Dinic finds it with repeated depth-first searches:

blockingFlow():
    it[v] = 0 for every v                     // current arc of v
    repeat:
        walk from s: at u take arc it[u] if it has room and goes one level down,
                     else it[u] = it[u] + 1
        reached t:   push b = min room on the path; full arcs drop out
        stuck at u:  u is a dead end; back up to the parent p and do it[p] + 1
        stuck at s:  return                   // blocking flow found

The current-arc pointer it[u] only moves forward during a phase. An arc it has passed is either full or leads to a dead end, and a dead end stays dead because flow in the level graph only ever fills arcs. So no arc is tried twice for nothing. (Demo: one phase, a dead end is pruned: after the paths s a c t, s a d t and s b d t, vertex d has no arc with room to level 3 and is pruned.)

Two phases on the sample network. Phase 1, distance 3: paths s a c t push 4, s a d t push 6, s b d t push 4, total 14, d becomes a dead end. Phase 2, distance 4: one path s b d c t pushes 5. Phase 3: BFS reaches only s and b; the cut s to a plus b to d has capacity 10 + 9 = 19.
Phase 1 pushes 14 along three paths of length 3; phase 2 needs length 4 and pushes 5; then the cut {s, b} proves 19 is the maximum.

Why there are few phases

After a blocking flow, every shortest path is blocked, so the next BFS finds t strictly farther away: dist(s, t) grows by at least 1 per phase (3, then 4 in the sample). A distance is at most V − 1, so there are at most V − 1 phases. One phase costs O(E) for the BFS and O(VE) for the blocking flow (each DFS walk is at most V edges plus the arcs it moves past, and each augmentation fills at least one arc). In total O(V2E), whatever the capacities.

Edmonds-KarpDinic
BFS runsone per augmenting pathone per phase
Paths per search1all shortest ones (blocking flow)
Running timeO(VE2)O(V2E)
Unit capacitiesO(VE)O(E √V) for bipartite matching (Hopcroft-Karp)

With large capacities the difference is plain: on the big capacities network (Demo: one phase pushes 2000) the edge a → b of capacity 1 joins two vertices of the same level, so it is never used and one phase pushes 1000 + 1000. A careless path choice could alternate through that edge 2000 times.

Back arcs still matter

The level graph is built from the residual graph, so a later phase can cancel flow. In the unit capacities network (Demo: a back arc reroutes flow → 2) phase 1 pushes 1 along s a b t; then b and c are dead ends because b → t is full. Phase 2 has distance 6 and its only path s c b a d e t runs backward over a → b, moving the first unit onto a → d → e → t.

When to stop: the minimum cut

When the BFS of a phase cannot reach t, the flow is maximum. The reached vertices are the source side of a minimum cut: every edge from them to the rest is full, and those capacities add up to the flow. In the sample the BFS reaches {s, b}; the cut edges are s → a (10) and b → d (9), and 10 + 9 = 19 (Demo: 3 phases → max flow 19). The proof is the max-flow min-cut theorem on the Ford-Fulkerson page.

Where it is used

  • Programming contests and graph libraries: Dinic with current arcs is the usual max-flow choice because it is short and fast on real inputs.
  • Bipartite matching: on a unit network Dinic is the Hopcroft-Karp algorithm.
  • Any problem reduced to max flow or min cut: disjoint paths, project selection, image segmentation.

What the page leaves out

Dynamic trees (Sleator-Tarjan), which bring a phase down to O(E log V); push-relabel algorithms; capacity scaling; the proof that unit networks need only O(√V) phases; and antiparallel edges, which the sample networks avoid.