Dinic's Algorithm (Max Flow)

Dinic's algorithm computes the maximum flow through a network — the most water you can push from a source S to a sink T given per-pipe capacity limits. It is the fast, interview-friendly upgrade over plain Ford–Fulkerson, and its trick is a clean two-phase loop: BFS to build levels, then DFS to push a blocking flow.

The slow way first

Plain Ford–Fulkerson finds one augmenting path at a time (any path with spare capacity), pushes flow along it, and repeats. It works, but it can waste effort: it may walk long, winding paths and, with awkward capacities, take a number of iterations that depends on the capacity values themselves — far too many.

The question to ask: can I find many augmenting paths at once, and only along the shortest routes? That is exactly what Dinic does.

The idea: BFS levels, then a blocking flow

Repeat two phases until you cannot reach the sink:

1. BFS phase. From S, run BFS on the residual graph and give every node a level = its distance from S. If T gets no level, stop — no more flow is possible.
2. DFS phase. Push flow with DFS, but only along level-respecting edges: an edge may carry flow only if it goes from level L to level L+1. Keep pushing paths until none remain. The result is a blocking flow for these levels.

Restricting DFS to level-increasing edges is the key: paths can only get longer over the phases, which bounds the number of phases and makes the whole thing fast.

Walk through it

Step through the animation. Phase 1: BFS labels S=0, A=1, B=1, T=2. DFS pushes 2 along S->A->T, then 2 along S->B->T — running total 4. Phase 2: BFS runs again on what capacity is left, but T can no longer be reached, so we stop and return 4.

Pseudocode

total = 0
repeat:
    level = BFS from S            # distance of each node from S
    if T has no level: stop       # sink unreachable -> done
    repeat:
        pushed = DFS from S to T, following only level L -> L+1 edges
        if pushed == 0: break     # blocking flow complete
        total += pushed
return total

The Python solution

def dinic(graph, s, t):
    total = 0
    while True:
        level = bfs(graph, s)        # assign distance levels
        if level[t] is None:         # sink unreachable
            break
        while True:
            pushed = dfs(graph, s, t, INF, level)
            if pushed == 0:
                break
            total += pushed          # add this path's flow
    return total

• total accumulates the maximum flow across all phases.
• bfs returns a level map (distance from s); it only follows residual edges with spare capacity.
• Line 5 is the stopping test — if T got no level, BFS could not reach it, so no more flow exists.
• The inner loop calls dfs, which pushes flow only along edges going from level L to level L+1, and returns the amount pushed.
• When dfs returns 0, the blocking flow for these levels is done; we run BFS again to relabel.

Complexity

Each phase strictly increases the BFS distance to T, so there are at most V phases; each phase's blocking flow costs O(V * E). That O(V^2 * E) bound is independent of the capacity values — a big win over plain Ford–Fulkerson.

When this pattern shows up

Practice