Dinic's Algorithm, in depth: level graphs, blocking flows, current-arc pointers and a max-flow implementation you can trust

First principles: residual graphs and augmenting paths

A flow assigns each edge (u, v) a value 0 <= f(u,v) <= c(u,v) such that every vertex except s and t has inflow equal to outflow. The residual graph records what can still change: a forward edge with residual capacity c(u,v) - f(u,v), and a reverse edge (v, u) with capacity f(u,v), which represents cancelling flow already sent. An augmenting path is any s-to-t path in the residual graph; pushing its bottleneck capacity along it increases the flow.

The max-flow min-cut theorem says the flow is maximum exactly when no augmenting path exists, and that its value then equals the capacity of the smallest s-t cut. The reverse edges are what make greedy augmentation correct: a bad early choice can always be undone later. The generic method and its proof are covered in Ford-Fulkerson maximum flow, and the shortest-path refinement in Edmonds-Karp in depth.

The two ideas: level graph and blocking flow

Run a BFS from s over residual edges with positive capacity and record level[v], the distance from s. The level graph keeps only edges (u, v) with level[v] == level[u] + 1. Every path from s to t in it is a shortest augmenting path, and it is a DAG, so a DFS in it can never loop.

A blocking flow in the level graph is a flow after which every s-t path in the level graph contains at least one saturated edge. It is not necessarily a maximum flow of the level graph; it only blocks every path. Dinic's algorithm is then three lines:

flow = 0
while BFS from s reaches t:            # build levels on the residual graph
    reset current-arc pointers
    flow += blocking_flow(level graph)  # repeated DFS with pointers
return flow

Why each phase makes progress

Let d be the BFS distance of t at the start of a phase. The key lemma: after the blocking flow, the new distance is strictly greater than d. Pushing flow only saturates level-graph edges, which go from level i to i+1, and only creates reverse edges going from level i+1 back to i. A path that uses any new reverse edge or any non-level edge loses at least one step of progress, so any s-t path of length d would have to be made entirely of level-graph edges, and the blocking flow saturated at least one edge on every such path. Hence no path of length d survives.

Distances are between 1 and V - 1, so there are at most V - 1 phases. Everything else is the cost of one blocking flow.

Current-arc pointers: the detail that makes it fast

The blocking flow is found by DFS from s in the level graph. Each vertex keeps a pointer it[u] into its adjacency list. The DFS tries edges from it[u] onward and advances the pointer past any edge that is saturated or leads to a dead end. Because the level graph only loses edges during a phase (pushing along level edges creates reverse edges that point to a lower level, which the level test rejects), an edge skipped once is useless for the rest of the phase.

That monotonicity gives the bound. Each augmenting path has at most V edges and saturates at least one, so a phase has at most E augmentations costing O(V) each, plus O(E) total pointer advances: O(VE) per phase and O(V^2 E) overall. Without the pointers the DFS re-explores dead ends, and the per-phase bound is gone. This is the single most common reason a "Dinic" from the internet times out.

An implementation tested against a reference

The version below stores edges in flat arrays, pairs each edge with its reverse at index e ^ 1, and finds paths with an explicit stack so deep graphs cannot overflow Python's recursion limit. It was checked against an Edmonds-Karp reference on 3,000 random graphs, including the cut capacity returned by min_cut_side.

from collections import deque

class Dinic:
    def __init__(self, n):
        self.n = n
        self.adj = [[] for _ in range(n)]   # edge ids per vertex
        self.to, self.cap = [], []          # edge e and its reverse e ^ 1

    def add_edge(self, u, v, c, rev_cap=0):
        self.adj[u].append(len(self.to)); self.to.append(v); self.cap.append(c)
        self.adj[v].append(len(self.to)); self.to.append(u); self.cap.append(rev_cap)

    def _bfs(self, s, t):
        self.level = [-1] * self.n
        self.level[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for e in self.adj[u]:
                v = self.to[e]
                if self.cap[e] > 0 and self.level[v] < 0:
                    self.level[v] = self.level[u] + 1
                    q.append(v)
        return self.level[t] >= 0

    def _augment(self, s, t):
        adj, to, cap, level, it = self.adj, self.to, self.cap, self.level, self.it
        path, u = [], s
        while True:
            if u == t:                       # push the bottleneck along the path
                f = min(cap[e] for e in path)
                for e in path:
                    cap[e] -= f
                    cap[e ^ 1] += f
                return f
            while it[u] < len(adj[u]):       # current arc: skip useless edges for good
                e = adj[u][it[u]]
                if cap[e] > 0 and level[to[e]] == level[u] + 1:
                    break
                it[u] += 1
            if it[u] < len(adj[u]):          # advance
                e = adj[u][it[u]]
                path.append(e)
                u = to[e]
            else:                            # dead end: retreat, kill parent's arc
                if u == s:
                    return 0
                e = path.pop()
                u = to[e ^ 1]
                it[u] += 1

    def max_flow(self, s, t):
        flow = 0
        while self._bfs(s, t):
            self.it = [0] * self.n
            while (f := self._augment(s, t)) > 0:
                flow += f
        return flow

    def min_cut_side(self):
        """Vertices reachable from s in the final residual graph."""
        return [v for v in range(self.n) if self.level[v] >= 0]

Undirected edges are added as add_edge(u, v, c, c), one edge pair with capacity in both directions. In C++ or Java the same structure is usually written with a recursive DFS; that is fine with a deliberately enlarged stack, but the iterative form avoids the question.

Worked example: the CLRS network

Take the network from Cormen et al.: s->v1 16, s->v2 13, v1->v3 12, v2->v1 4, v2->v4 14, v3->v2 9, v3->t 20, v4->v3 7, v4->t 4. Numbering s=0, v1..v4=1..4, t=5, the implementation above produces this trace:

In phase 1, the first DFS takes s-v1-v3-t and saturates v1->v3 (12). The second finds s-v2-v4-t and saturates v4->t (4). Now every length-3 path is blocked. In phase 2 the BFS reaches v3 only through v4, so t moves to level 4, exactly as the lemma predicts. One path of bottleneck 7 saturates v4->v3. The third BFS reaches {s, v1, v2, v4} and stops.

That reachable set is the minimum cut. The edges leaving it are v1->v3 (12), v4->v3 (7) and v4->t (4), totalling 23, equal to the flow. Edge v3->v2 points into the set and does not count. Reading the cut from the last BFS is free, and it is often the answer you actually wanted: which constraints are binding.

Complexity in the cases that matter

Worst-case bounds are pessimistic; on most practical graphs Dinic finishes in a handful of phases. Bipartite matching is the common contest and production case: connect s to every left vertex and every right vertex to t with capacity 1, give the middle edges capacity 1, and the max flow is the maximum matching. Compare the augmenting-path view in Kuhn's bipartite matching. For very dense or adversarial graphs, push-relabel with the highest-label rule and gap heuristics is often faster in practice.

Modelling: getting a problem into flow form

Most of the work in applying Dinic is the reduction, not the solver. Two patterns cover a large share of real uses. Vertex capacities: split each limited vertex v into v_in and v_out joined by an edge with the vertex's capacity, and route all incoming edges to v_in and outgoing edges from v_out. Project selection: each project with profit p > 0 gets an edge s -> project of capacity p, each required resource with cost c gets resource -> t of capacity c, and each dependency gets an infinite edge project -> resource. The best net profit is the sum of positive profits minus the max flow, and the chosen projects are the ones on the s side of the min cut. The infinite edges are what forbid choosing a project without paying for its resources, because a finite cut can never cross them.

Failure modes

Two operational notes. First, the residual state after max_flow is the flow itself: original capacity minus residual gives f(u,v) on each forward edge, which is how you recover an actual matching or routing. Second, if you need many max-flow queries on slightly different graphs, think about the reduction before the solver; a min-cost or parametric formulation may answer them all at once. Basic BFS mechanics are in BFS and DFS.

What to do next

1. Copy the implementation, then write a brute-force or Edmonds-Karp checker and compare on a few thousand random small graphs before trusting it.
2. Trace the CLRS network by hand and confirm the levels and paths in the table above.
3. Model one bipartite matching problem from your own work as flow and read the matching from saturated middle edges.
4. Extract the min cut with min_cut_side and list the binding edges.
5. Remove the current-arc pointer, time both versions on a dense graph, and see the difference yourself.
6. Read about push-relabel and capacity scaling, and decide which fits your largest graphs.