Dinic’s Algorithm

Dinic’s algorithm (Dinitz, 1970) is an asymptotically faster method for the Maximum Flow problem, running in O(V² · E) time on general graphs and O(E · √V) on graphs whose every capacity is 1 (so-called unit-capacity networks). The algorithm operates in phases: each phase first builds a level graph by running Breadth-First Search from the source s, retaining only the edges that strictly increase BFS-distance to the sink t; then it computes a blocking flow in that level graph by DFS-style traversal, saturating at least one edge on every s → t path. Because every phase strictly increases the shortest-path distance from s to t in the residual graph, and that distance is bounded by V, the algorithm terminates in O(V) phases. Dinic’s is the basis of the celebrated Hopcroft-Karp bipartite-matching algorithm — which is just Dinic’s specialized to the unit-capacity bipartite-graph case — and remains a strong choice in practice when capacities are small or the graph is dense.

1. Intuition — Doing All the Work for One Shortest-Distance “Layer” at Once

Edmonds-Karp picks one shortest augmenting path per iteration, augments along it, then re-runs BFS from scratch. But many of those BFS computations rediscover the same shortest-path distances. Dinic’s observation: between two iterations of Edmonds-Karp where the shortest s→t distance hasn’t changed, we are essentially still working “at the same level.” Why not extract all augmenting paths at the current shortest-distance level in a single phase, then move on?

That’s exactly what a phase does:

1. BFS from s to compute level[v], the shortest distance from s to each vertex in the residual graph. If t is unreachable, the algorithm halts — we’re done.
2. Construct the level graph: keep only edges (u, v) with level[v] = level[u] + 1 (strictly forward in the BFS tree) and positive residual capacity.
3. Find a blocking flow in the level graph — a flow that saturates at least one edge on every s → t path of the level graph. Equivalently: in the level graph, after sending the blocking flow, there is no path of positive-residual edges from s to t.
4. Add the blocking flow to the global flow. Update residuals. Go back to step 1.

The blocking-flow concept is the heart of the speedup. A single blocking flow may consist of many augmenting paths, but they’re computed together in one DFS-style sweep through the level graph rather than via repeated BFSes. The cost of a phase is O(V · E) (proven below), and the number of phases is O(V) (since each phase strictly increases d(s, t)), giving O(V² · E) total.

The intuition for the unit-capacity speedup: in a unit-capacity graph, each edge can carry at most 1 unit of flow, so saturating any edge ends its useful life. The total “work” is bounded much more tightly, leading to O(E · √V).

2. Concepts: Level Graph and Blocking Flow

2.1 Level Graph

Given a residual graph G_f, the level graph G_L is built by:

1. Running BFS from s in G_f, computing level[v] for every reachable v.
2. Including edge (u, v) in G_L if and only if (u, v) ∈ G_f (with positive residual capacity) AND level[v] = level[u] + 1.

This gives a layered DAG (directed acyclic graph): edges only go from level k to level k + 1, never sideways or backward. If t is unreachable from s in G_f, then level[t] is undefined and the algorithm has converged.

2.2 Blocking Flow

A blocking flow in a graph H is a flow f_b such that every directed s → t path in H contains at least one edge saturated by f_b (i.e., its residual under f_b is zero). A blocking flow is not the maximum flow in H in general — it is just “stuck” in the sense that you can’t find any further s → t path of strictly positive residual edges. In a level graph, however, a blocking flow turns out to be a particularly good intermediate object.

Why blocking flow is enough. In the level graph, every s → t path has length exactly level[t] (by construction). After computing the blocking flow, every such path has at least one saturated edge. Crucially, augmenting paths of this same length are now impossible in the full residual graph, because any such path projects to a level-graph path. So level[t] strictly increases in the next phase.

Computing the blocking flow. The classical method is iterative DFS with a clever dead-end pruning trick (sometimes called the “current arc” optimization, attributed to Tarjan):

• DFS from s, advancing along the level graph.
• When the DFS reaches t, push flow equal to the bottleneck along the s→t path, update residuals, and resume.
• When the DFS at vertex u finds that all outgoing edges either lead to dead ends or have zero residual, mark u as “exhausted” — future DFS visits from elsewhere should skip u’s exhausted edges. This is the key amortization that prevents repeated wasted exploration.

A standard implementation uses an iter[u] pointer per vertex that advances through u’s adjacency list and never resets within a phase; this gives the O(V·E) per-phase bound.

3. Tiny Worked Example

We’ll reuse the network from Maximum Flow §4 to compare against Edmonds-Karp.

Edges with capacities:

s → a : 10
s → b : 10
a → b :  1
a → t :  5
b → t : 10

Phase 1.

BFS from s in residual graph: level[s]=0, level[a]=1, level[b]=1, level[t]=2 (reachable via a→t or b→t).

Level graph: edges where level[v] = level[u] + 1 with positive residual:

• s→a (0→1): cap 10 ✓
• s→b (0→1): cap 10 ✓
• a→t (1→2): cap 5 ✓
• b→t (1→2): cap 10 ✓
• a→b (1→1): excluded (same level)

Blocking flow via DFS in level graph:

• DFS s → a → t, bottleneck 5. Push 5. Now a→t is saturated; s→a has 5 left.
• DFS s → a (now a has no outgoing usable edge in the level graph — a→t is saturated, a→b was excluded). Mark a exhausted.
• DFS s → b → t, bottleneck min(10, 10) = 10. Push 10. Now b→t saturated; s→b has 0 left.
• DFS from s: no usable outgoing edges. Phase done.

Blocking flow value: 5 + 10 = 15. Total flow so far: 15.

Phase 2.

BFS in residual graph: outgoing from s: s→a cap 5 (after phase 1), s→b cap 0. So only a is at level 1. From a: a→t cap 0, a→b cap 1 (forward), a→s cap 5 (reverse, cycle). So b is at level 2. From b: b→t cap 0, b→a cap 0 (was 0 originally), b→s cap 10 (reverse). t is unreachable. Halt.

Total max flow: 15. Phases used: 2 (with 1 BFS each, so a total of 2 BFSes — Edmonds-Karp would have done 3 or more, with each iteration finding a single path).

The number of phases scales with the diameter of the residual graph layered structure, not with the capacity values.

4. Pseudocode

dinic(G, s, t):
    initialize residual graph G_f
    total := 0
    while True:
        level := bfs_levels(G_f, s)
        if level[t] is undefined:
            return total                      # no s-t path → done
        # Build level graph implicitly via the level array
        iter[u] := 0 for every u             # pointer into u's adjacency list
        while True:
            pushed := dfs_blocking(s, t, ∞, level, iter, G_f)
            if pushed == 0:
                break                          # blocking flow complete
            total := total + pushed

dfs_blocking(u, t, in_flow, level, iter, G_f):
    if u == t:
        return in_flow
    while iter[u] < len(adj[u]):
        v := adj[u][iter[u]]
        c := residual_capacity(u, v)
        if c > 0 and level[v] == level[u] + 1:
            d := dfs_blocking(v, t, min(in_flow, c), level, iter, G_f)
            if d > 0:
                push d along (u, v)            # decrement c_f(u,v), increment c_f(v,u)
                return d                       # do NOT advance iter[u]
        iter[u] := iter[u] + 1                 # exhausted this edge for this phase
    return 0

The subtlety is the placement of iter[u] += 1: when DFS fails through an edge (returns 0), we advance the pointer, “blacklisting” that edge for the rest of this phase. When DFS succeeds (returns positive), we keep iter[u] where it is so the next augmentation can re-attempt the same edge if it still has capacity. This is what makes one phase amortize to O(V·E) rather than O(V·E²).

5. Python Implementation

from collections import defaultdict, deque
 
class Dinic:
    def __init__(self):
        self.adj = defaultdict(list)        # adj[u] is list of edge indices
        self.edges = []                     # each entry: [to, cap]
        # Edge with index i has its reverse at i ^ 1 (paired adjacent indices)
 
    def add_edge(self, u, v, c):
        self.adj[u].append(len(self.edges))
        self.edges.append([v, c])
        self.adj[v].append(len(self.edges))
        self.edges.append([u, 0])           # reverse edge starts at 0
 
    def bfs(self, s, t):
        self.level = {s: 0}
        q = deque([s])
        while q:
            u = q.popleft()
            for eid in self.adj[u]:
                v, c = self.edges[eid]
                if c > 0 and v not in self.level:
                    self.level[v] = self.level[u] + 1
                    q.append(v)
        return t in self.level
 
    def dfs(self, u, t, in_flow):
        if u == t:
            return in_flow
        while self.iter[u] < len(self.adj[u]):
            eid = self.adj[u][self.iter[u]]
            v, c = self.edges[eid]
            if c > 0 and self.level.get(v, -1) == self.level[u] + 1:
                pushed = self.dfs(v, t, min(in_flow, c))
                if pushed > 0:
                    self.edges[eid][1] -= pushed
                    self.edges[eid ^ 1][1] += pushed
                    return pushed
            self.iter[u] += 1
        return 0
 
    def max_flow(self, s, t):
        total = 0
        while self.bfs(s, t):
            self.iter = defaultdict(int)
            while True:
                pushed = self.dfs(s, t, float('inf'))
                if pushed == 0:
                    break
                total += pushed
        return total

Implementation notes.

• Edge pairing trick: edges are stored in a flat list, and each edge i has its reverse at index i ^ 1 (XOR with 1). This works because we always add forward and reverse edges in immediate succession, so consecutive even/odd indices form a pair. This avoids the dict-of-dicts approach and is significantly faster.
• level.get(v, -1) handles the case where v is unreachable in BFS — it returns -1 which can never equal level[u] + 1.
• iter[u] is the “current arc” pointer; resetting it once per phase (in max_flow) is critical.
• Recursion depth: the recursive DFS will exceed Python’s default 1000-frame recursion limit on long paths. Either sys.setrecursionlimit or rewrite as iterative DFS for production use.

6. Complexity Analysis

6.1 Number of phases is O(V)

Claim. Across consecutive phases, the BFS distance level[t] (i.e., d(s, t) in the residual graph) strictly increases.

Proof sketch. After a phase, every s → t path of length exactly level[t] in the level graph has at least one saturated edge (definition of blocking flow). Consider the residual graph after the phase: any new s → t path either (a) uses only level-graph edges, in which case it must be longer because some edge of the old length-level[t] path is now gone, or (b) uses at least one edge that wasn’t in the level graph — either a “reverse” edge created by augmentation or an edge (u, v) that wasn’t in the level graph because level[v] ≠ level[u] + 1. In all such cases, the new shortest path has length strictly greater than the old level[t].

A more rigorous version uses the same monotone-distance lemma as in Edmonds-Karp §6.1, plus the observation that after a blocking flow, no s → t path of length equal to the old level[t] survives.

Since level[t] ≤ V − 1 and increases by at least 1 each phase, there are at most V − 1 = O(V) phases.

6.2 Each phase costs O(V · E)

Claim. The blocking-flow computation in one phase runs in O(V · E).

Proof sketch. Consider the entire phase as a series of DFS calls from s. Each DFS call either:

• Finds an augmenting path and pushes flow, saturating at least one edge on that path, or
• Returns to a vertex with no usable outgoing edge, advancing iter[u] on that vertex.

The number of edge-saturations per phase is at most E (each edge can be saturated at most once per phase — once saturated, it’s gone from the level graph until residuals change in the next phase). Each augmenting path has length at most V, so the work per augmentation is O(V), giving O(V · E) for all augmentations combined.

The advances of iter[u] are bounded too: across the whole phase, each vertex u has at most degree(u) advances of iter[u]. Summing: Σ degree(u) = O(E). So total iter advances cost O(E).

Combining: O(V · E) for augmentation + O(E) for dead-end pruning = O(V · E) per phase.

6.3 Total: O(V² · E)

O(V) phases × O(V · E) per phase = O(V² · E). □

6.4 Unit-capacity special case: O(E · √V)

When every capacity is 1 (or, more generally, every vertex has either in-degree ≤ 1 or out-degree ≤ 1 — the “unit network” condition), Dinic’s runs in O(E · √V). The argument is two-pronged:

• For the first O(√E) phases (or in unit networks the first √V phases), each phase costs O(E) rather than O(V · E) because each augmenting path saturates a distinct edge and there are no useful cycles.
• After O(√V) phases, the remaining flow is at most O(√V) units (a counting argument based on the layered structure), and we do at most O(√V) more phases.

Total: O(√V · E). The full proof is in Even & Tarjan (1975) and Hopcroft & Karp (1973). The unit-capacity bound is what makes Hopcroft-Karp for Bipartite Matching achieve O(E · √V) — Hopcroft-Karp is essentially Dinic’s algorithm specialized to bipartite matching’s natural unit-capacity structure.

7. Variants

7.1 Capacity-scaling Dinic’s

Combine Dinic’s with capacity scaling: only consider edges of residual capacity ≥ Δ where Δ halves each outer iteration. Improves the worst case for graphs with very large capacities.

7.2 Link-cut tree variant (Sleator-Tarjan)

Use link-cut trees to compute the blocking flow in O(E · log V) per phase instead of O(V · E). Total: O(V · E · log V). Theoretically appealing; rarely faster in practice due to large constants.

7.3 MPM algorithm (Malhotra, Pramodh-Kumar, Maheshwari, 1978)

A different blocking-flow strategy giving O(V³) total — better than Dinic’s for dense graphs (E ≈ V²) but worse for sparse.

7.4 Push-relabel (Goldberg-Tarjan, 1986)

A different paradigm entirely — abandons augmenting paths, instead pushes “preflow” greedily. Achieves O(V²·√E) and is what most production max-flow libraries (Boost Graph, LEMON, OR-Tools) implement.

8. Common Interview Problems

Problem	How Dinic’s helps
LC 1947 — Maximum Compatibility Score Sum	Bipartite matching → Hopcroft-Karp / Dinic’s unit-cap
Classic: bipartite matching	Hopcroft-Karp = Dinic’s on bipartite unit-cap → O(E·√V)
Edge-disjoint paths in unit-capacity graphs	O(E·√V) — essentially the only practical algorithm at scale
Vertex connectivity / k-connectivity testing	Dinic’s between vertex pairs after vertex-splitting
Image segmentation (graph cuts) at video framerate	Dinic’s or push-relabel; Dinic’s wins on small dense graphs

For most algorithmic interviews, describing Dinic’s (level graph + blocking flow + O(V²·E)) is sufficient — the interviewer rarely expects a full implementation under time pressure. Be ready to contrast it with Edmonds-Karp (“Edmonds-Karp picks one shortest path per iteration; Dinic’s exhausts all paths at the current shortest distance per phase”).

9. Pitfalls

9.1 Forgetting the iter[u] “current arc” pointer

Without it, each DFS call rediscovers dead ends from scratch, blowing the per-phase complexity from O(V·E) to O(V·E²) and therefore total to O(V³·E²). The pointer is the difference between “Dinic’s algorithm” and “a slow blocking-flow computation.”

9.2 Resetting iter[u] mid-phase

iter[u] must be reset only between phases (each new BFS resets the level graph, so old iter values become irrelevant). Resetting within a phase ruins the amortization — you lose the work of all previous DFS calls.

9.3 BFS that doesn’t reset level between phases

Each new phase computes a fresh level array. Forgetting to clear it leaves stale entries that cause level[v] == level[u] + 1 to spuriously pass.

9.4 Including same-level edges in the level graph

Edges (u, v) with level[u] == level[v] or level[v] == level[u] (i.e., not strictly forward) must NOT be included. Including them creates cycles and breaks the DAG structure that the blocking-flow algorithm relies on. Only include level[v] == level[u] + 1.

9.5 Recursive DFS stack overflow

The blocking-flow DFS can recurse to depth V. In Python, raise the recursion limit or rewrite iteratively. In C++, watch the default 1MB stack on contest judges.

9.6 Not pairing forward/reverse edges

If forward and reverse edges are added separately and indexed independently, the i ^ 1 reverse-edge trick fails. Always add forward and reverse in immediate succession.

9.7 Believing Dinic’s is “always faster” than Edmonds-Karp

For small graphs (under ~100 vertices), the constant-factor overhead of level-graph construction often makes Dinic’s slower than Edmonds-Karp in wall-clock time. Profile before optimizing. The asymptotic win matters at scale (thousands of vertices, millions of edges).

9.8 Confusing blocking flow with maximum flow

A blocking flow in a level graph is not the maximum flow of the original graph; it’s just an intermediate result. The algorithm needs multiple phases (each producing a blocking flow) before reaching the global maximum.

10. Diagram — Phase Structure

flowchart TB
  subgraph PhaseLoop["Phase Loop (≤ V iterations)"]
    A["BFS from s<br/>compute level[v]"] --> B{"t reachable?"}
    B -->|no| END((Return total flow))
    B -->|yes| C["Build level graph:<br/>keep edges (u,v)<br/>with level[v]=level[u]+1"]
    C --> D["Compute blocking flow<br/>via DFS with iter[u]"]
    D --> E["Add blocking flow<br/>to total"]
    E --> A
  end

What this diagram shows. Each iteration of the outer loop is one phase of Dinic’s. A phase begins by computing BFS distances from s in the current residual graph. If t is unreachable, we are done. Otherwise, we build the level graph and compute a blocking flow. The blocking-flow computation is itself a loop (DFS-find-and-augment until no s→t path remains in the level graph), but conceptually counts as one phase. After the blocking flow, residuals are updated and the next phase begins. There are at most V − 1 phases because level[t] increases by at least 1 each phase. This nested loop structure — outer phases bounded by V, inner phase work bounded by V·E — is what gives O(V² · E).

11. Open Questions

• What is the practical crossover point where Dinic’s beats Edmonds-Karp on benchmark instances? (Empirically: graphs with V ≥ ~1000 and integer capacities, often Dinic’s wins; sparse small graphs Edmonds-Karp wins.)
• How does the O(E · √V) bound for unit-capacity Dinic’s relate to Hopcroft-Karp? (Answer: Hopcroft-Karp is Dinic’s specialized to bipartite matching; the √V bound is identical and the algorithms are conceptually the same.)
• Can blocking flows be computed even faster? (Yes — the link-cut tree variant gives O(E · log V) per phase, and Sleator-Tarjan’s analysis gives O(V · E · log V) overall. Not used in practice.)

12. See Also

• Maximum Flow — the meta-algorithm Dinic’s specializes
• Edmonds-Karp — simpler but slower (O(V·E²))
• Min-Cut Max-Flow Theorem — what the final flow witnesses
• Bipartite Matching — application: cap=1 bipartite case
• Hopcroft-Karp — Dinic’s specialized to bipartite matching → O(E·√V)
• Breadth-First Search — used to compute level[v]
• Depth-First Search — used inside blocking-flow computation
• Big-O Notation
• SWE Interview Preparation MOC