Algorithms · Graphs

Push Water Through a Network of Pipes.

Pipes have capacities; how much water can flow from source to sink? Dinic's algorithm is the fast answer: layer the graph by distance from the source with a BFS, then flood all the shortest paths at once with a single DFS “blocking flow,” rebuild the layers, and repeat. Each round the source and sink drift further apart — so it finishes in O(V²E).

O(V²E) · BFS levels + DFS blocking flow · max-flow / min-cut
capacity

Each edge shows flow / cap — how much it carries vs. its limit.

level graph

BFS labels each node with its distance from the source; only next-level edges count.

blocking flow

One DFS saturates every shortest path until none has spare room.

phase

Rebuild the levels and repeat; the sink gets farther each phase, so few phases suffice.

dinic.js — BFS levels, DFS blocking flow, repeat
Ready
A flow network from source s (green) to sink t (purple); edges show flow / capacity. Press Step: first a BFS assigns each node a level (distance from s). Then a DFS pushes flow along level-climbing paths (orange) until each is saturated. Rebuild levels, repeat, until s can't reach t.
0
phase
last push
0
max flow

How it works

The basic max-flow idea — find a source-to-sink path with spare capacity, push flow, repeat — can waste time on long, winding paths. Dinic's insight is to always push along shortest paths first, and to do a whole batch of them per BFS. Because the shortest source-to-sink distance strictly grows after each blocking flow, there can be at most V phases.

1

Build the level graph (BFS)

From the source, BFS over edges with spare capacity; each node's level is its hop-distance. If the sink is unreachable, the current flow is maximum — stop.

2

Push a blocking flow (DFS)

DFS from source to sink using only edges from level L to level L+1. Each path pushes its bottleneck capacity; saturated edges drop out.

3

Reuse work per node

An iterator pointer per node skips edges already known to be dead this phase, so the whole blocking flow is found in O(VE) — not one slow DFS per path.

Repeat until disconnected

Rebuild the levels and push again. Distances increase each phase, so after ≤ V phases the sink falls out of the level graph and you have the max flow.

General
O(V²E)
Unit caps
O(E√V)
Bipartite match
O(E√V)
This demo
flow = 19

The code

def max_flow(s, t): flow = 0 while bfs_levels(s, t): # build level graph; stop if t unreachable it = [0] * V # per-node edge iterator while True: pushed = dfs(s, t, INF, it) # one augmenting path in the level graph if pushed == 0: break flow += pushed return flow def dfs(u, t, f, it): if u == t: return f while it[u] < len(g[u]): e = g[u][it[u]] if e.cap - e.flow > 0 and level[e.to] == level[u] + 1: d = dfs(e.to, t, min(f, e.cap - e.flow), it) if d > 0: e.flow += d; e.rev.flow -= d; return d it[u] += 1 # dead edge — skip it next time too return 0

The two-line trick that makes it fast is the shared iterator it[]: once the DFS proves an edge leads nowhere useful this phase, the pointer advances past it and never reconsiders it, so building a blocking flow costs O(VE) total rather than O(E) per path. By the max-flow / min-cut theorem, the value Dinic returns also equals the capacity of the smallest cut separating source from sink — the graph's true bottleneck.

Quick check

1. Why does Dinic build a BFS level graph before pushing flow?

2. What does a "blocking flow" mean within one level graph?

FAQ

What is the maximum-flow problem?

The most that can flow from a source to a sink through capacitated edges, with flow conserved at every other node.

What is a level graph?

A BFS labelling of nodes by distance from the source; Dinic only pushes flow along edges that step from one level to the next.

What is a blocking flow?

A flow in the level graph where every s–t path has a saturated edge, so no more can be pushed without rebuilding the levels.

How fast is it?

O(V²E) in general, O(E√V) on unit-capacity graphs and bipartite matching — much faster than basic Ford–Fulkerson.

Keep going

Finished this one? 0 / 62 Algorithms done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

More Algorithms