Dinic's Max Flow

How Dinic's algorithm works

Maximum flow asks a simple question with messy mechanics: pump as much as possible from a source s to a sink t through a network of capacitated pipes. The Ford-Fulkerson method answers it by finding any augmenting path with spare capacity and pushing flow along it, over and over, until none remains. The trouble is "any path" can be pathological — choose badly and you augment by a trickle each time, blowing up to a runtime that depends on the capacity values, not just the graph size.

Edmonds-Karp tamed that by always taking the shortest augmenting path (fewest edges) via BFS. Dinic's algorithm, published by Yefim Dinitz in 1970 — a year before Edmonds and Karp's paper — goes one step further. Instead of pushing one shortest path per BFS, it pushes all of them at once, then rebuilds. The algorithm runs in phases:

1. Build the level graph. Run a BFS from s on the residual network, labelling each vertex with its distance (its level). Keep only edges that go from level L to level L+1. If t is unreachable, you are done — the current flow is maximum.
2. Find a blocking flow. Push flow through the level graph until every s→t path has at least one saturated edge. This is done with a DFS that prunes dead-end vertices so they are never revisited within the phase.
3. Repeat. Each phase strictly increases the shortest s-to-t distance, so the loop runs at most V − 1 times.

The key insight is that the level graph is the union of every shortest augmenting path simultaneously. Saturate it fully — that's the blocking flow — and the shortest path the next BFS can find is guaranteed to be longer. That monotone-distance argument is what bounds the number of phases by the number of vertices.

The level graph and blocking flow

A residual network stores, for each edge, the remaining capacity cap − flow, plus a back-edge with capacity equal to the flow already pushed (so flow can be "undone"). BFS over this residual network assigns level[v] = shortest edge-distance from s. The level graph L is the subgraph of residual edges (u, v) with level[v] = level[u] + 1 and positive residual capacity.

Because every edge in L moves strictly one level closer to t, the level graph is a DAG, and any s→t path in it has exactly level[t] edges — the current shortest distance. A blocking flow is a flow on L such that no augmenting path of length level[t] survives; at least one edge on every such path is saturated. It is not necessarily the maximum flow on L — only "blocked" — but that is enough to force progress.

The clever part is the DFS that builds the blocking flow. A naive DFS would re-explore the same dead ends repeatedly. Dinic keeps a per-vertex iterator (the "current arc" pointer) that only advances: once an edge is found useless in this phase, it is never reconsidered. This is why a single blocking-flow phase costs only O(VE) rather than O(E) per path.

Complexity: where O(V²E) comes from

The runtime is a product of two bounds:

• Number of phases ≤ V − 1. Each phase increases level[t] by at least one. Distance can be at most V − 1 edges, so the algorithm terminates after at most V − 1 level-graph rebuilds.
• Cost per phase = O(VE). The DFS performs at most O(VE) work: each of the E edges is either saturated (advancing the augment) or skipped permanently via the current-arc pointer, and each augmenting path within the phase has length ≤ V.

Multiply: (V − 1) × O(VE) = O(V²E). Two special cases sharpen this dramatically:

• Unit-capacity networks: O(E√V). When every capacity is 1, a blocking flow costs just O(E), and the number of phases is bounded by O(√E). This is the exact bound behind Hopcroft-Karp bipartite matching.
• Unit-capacity, in/out-degree ≤ 1 (e.g. bipartite matching): O(E√V) — the matching special case, proven by Hopcroft and Karp in 1973.
• Planar networks and small integer capacities admit even tighter analyses, though general flow has since been pushed to near-linear time by the 2022 Chen–Kyng–Liu–Peng–Probst Gutenberg–Sachdeva almost-linear algorithm — a theoretical milestone, not yet a practical replacement.

When to choose Dinic

• Bipartite matching. Dinic on a unit-capacity network is Hopcroft-Karp — the standard O(E√V) matching algorithm.
• Dense flow networks where E is much larger than V; the V²E bound crushes Edmonds-Karp's VE².
• Image segmentation, project selection, baseball elimination, and min-cut reductions — anything that reduces to max-flow/min-cut. Dinic is the default workhorse in competitive programming for exactly these.
• Edge-disjoint and vertex-disjoint path counting, which become unit-capacity flow.

If your graph is small or you only need clarity, plain Edmonds-Karp is easier to write correctly. If capacities are gigantic and the graph is sparse, push-relabel (with the highest-label or gap heuristic) often beats Dinic in practice. But for the common case — moderate graphs, mixed capacities — Dinic is the sweet spot of speed and implementation simplicity.

Dinic vs other max-flow algorithms

	Dinic	Edmonds-Karp	Ford-Fulkerson (DFS)	Push-Relabel (FIFO)	Push-Relabel (highest-label)	BK (Boykov-Kolmogorov)
Worst-case time	O(V²E)	O(VE²)	O(E · maxflow)	O(V³)	O(V²√E)	worst-case poor, fast in vision
Unit-capacity	O(E√V)	O(VE²)	O(VE)	O(V³)	O(V²√E)	n/a
Strategy	blocking flow on level graph	one shortest path / BFS	any augmenting path	local push + relabel	local push + relabel	two search trees, reused
Terminates on irrational caps	yes	yes	not guaranteed	yes	yes	yes
Practical on dense graphs	good	slow	unreliable	excellent	excellent	graph-dependent
Implementation effort	moderate	low	lowest	moderate-high	high	high
Best for	matching, contests, min-cut	teaching, small graphs	tiny / integer-cap demos	large dense networks	large dense networks	computer-vision energy minimization

The headline contrast is Dinic vs Edmonds-Karp. They both use BFS and shortest paths, but Edmonds-Karp pays for a full BFS per augmenting path, while Dinic amortizes one BFS across an entire blocking flow. Whenever E > V — true for nearly all real graphs — V²E < VE², and the speedup is a factor of E/V.

What the numbers actually say

• On a dense graph with V = 1,000 and E = 100,000, Edmonds-Karp's worst case is on the order of VE² ≈ 10¹³ operations; Dinic's is V²E ≈ 10¹¹ — a 100× gap that is the difference between minutes and milliseconds.
• Bipartite matching with V = 10,000 vertices and E = 200,000 edges: Dinic finishes in O(E√V) ≈ 200,000 × 100 = 2 × 10⁷ operations — well under a second — versus the naive O(VE) = 2 × 10⁹ Hungarian-style augmenting.
• Phases are rarely worst case. On typical contest inputs the number of phases is closer to O(√V) or even constant, not V, so observed runtimes often beat the bound by a wide margin.
• The current-arc pointer is not optional. With it, an entire blocking-flow phase is O(VE). Drop it and the DFS re-walks dead ends, so each of the up-to-O(E) augmenting paths in a phase costs O(E) on its own — the phase balloons to roughly O(E²), turning the whole algorithm into something far worse than Edmonds-Karp.

JavaScript implementation

class Dinic {
  constructor(n) {
    this.n = n;
    this.to = []; this.cap = []; this.next = [];
    this.head = new Array(n).fill(-1);
    this.level = new Array(n);
    this.iter = new Array(n);
  }
  // add a directed edge u->v with capacity c (and a 0-cap reverse edge)
  addEdge(u, v, c) {
    this.to.push(v); this.cap.push(c); this.next.push(this.head[u]); this.head[u] = this.to.length - 1;
    this.to.push(u); this.cap.push(0); this.next.push(this.head[v]); this.head[v] = this.to.length - 1;
  }
  bfs(s, t) {
    this.level.fill(-1);
    const q = [s]; this.level[s] = 0;
    for (let i = 0; i < q.length; i++) {
      const u = q[i];
      for (let e = this.head[u]; e !== -1; e = this.next[e]) {
        if (this.cap[e] > 0 && this.level[this.to[e]] < 0) {
          this.level[this.to[e]] = this.level[u] + 1;
          q.push(this.to[e]);
        }
      }
    }
    return this.level[t] >= 0;          // is sink still reachable?
  }
  // DFS that pushes flow along the level graph; iter[] is the current-arc pointer
  dfs(u, t, f) {
    if (u === t) return f;
    for (; this.iter[u] !== -1; this.iter[u] = this.next[this.iter[u]]) {
      const e = this.iter[u], v = this.to[e];
      if (this.cap[e] > 0 && this.level[v] === this.level[u] + 1) {
        const d = this.dfs(v, t, Math.min(f, this.cap[e]));
        if (d > 0) {
          this.cap[e] -= d;
          this.cap[e ^ 1] += d;          // reverse edge (paired by XOR 1)
          return d;
        }
      }
    }
    return 0;
  }
  maxflow(s, t) {
    let flow = 0;
    while (this.bfs(s, t)) {            // one phase = one level graph
      for (let i = 0; i < this.n; i++) this.iter[i] = this.head[i];
      let f;
      while ((f = this.dfs(s, t, Infinity)) > 0) flow += f;  // blocking flow
    }
    return flow;
  }
}

// Example: 4 nodes, source 0, sink 3
const g = new Dinic(4);
g.addEdge(0, 1, 3); g.addEdge(0, 2, 2);
g.addEdge(1, 2, 1); g.addEdge(1, 3, 2);
g.addEdge(2, 3, 3);
console.log(g.maxflow(0, 3));          // => 5

Two details make this fast and correct. First, edges are stored in a flat array and paired so that edge e and its reverse are e and e ^ 1 — XOR-1 gives the back-edge in O(1) with no bookkeeping. Second, iter[u] advances and never resets within a phase, which is precisely the current-arc optimization that gives the O(VE) per-phase bound.

Python implementation

from collections import deque

class Dinic:
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]   # graph[u] = list of [v, cap, rev_index]

    def add_edge(self, u, v, c):
        self.graph[u].append([v, c, len(self.graph[v])])
        self.graph[v].append([u, 0, len(self.graph[u]) - 1])  # reverse edge

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

    def dfs(self, u, t, f):
        if u == t:
            return f
        while self.it[u] < len(self.graph[u]):
            edge = self.graph[u][self.it[u]]
            v, cap, rev = edge
            if cap > 0 and self.level[v] == self.level[u] + 1:
                d = self.dfs(v, t, min(f, cap))
                if d > 0:
                    edge[1] -= d
                    self.graph[v][rev][1] += d
                    return d
            self.it[u] += 1            # current-arc pointer advances
        return 0

    def max_flow(self, s, t):
        flow = 0
        while self.bfs(s, t):          # one phase per level graph
            self.it = [0] * self.n
            while True:
                f = self.dfs(s, t, float('inf'))
                if f == 0:
                    break
                flow += f              # accumulate the blocking flow
        return flow

g = Dinic(4)
g.add_edge(0, 1, 3); g.add_edge(0, 2, 2)
g.add_edge(1, 2, 1); g.add_edge(1, 3, 2)
g.add_edge(2, 3, 3)
print(g.max_flow(0, 3))               # => 5

The Python version keeps the reverse-edge index explicitly (rev) since lists don't give the XOR trick. Otherwise it is the same two-loop structure: BFS rebuilds the level graph, then a sequence of DFS augmentations drains it into a blocking flow before the next phase.

Variants worth knowing

Scaling Dinic. Process capacities in decreasing powers of two: in the Δ-scaling phase only consider residual edges with capacity ≥ Δ. This gives O(VE log U) where U is the max capacity — better than O(V²E) when U is small relative to V.

Link-cut tree Dinic (Sleator-Tarjan). Replace the blocking-flow DFS with a dynamic-tree data structure to push flow along whole paths in O(log V), reducing each phase to O(E log V) and the total to O(VE log V). Beautiful in theory, rarely worth the constant factor in practice.

Hopcroft-Karp. Dinic specialized to the unit-capacity bipartite-matching network, running in O(E√V). If someone hands you Hopcroft-Karp, you are looking at Dinic in disguise.

Push-relabel. A different paradigm entirely — maintain a preflow and locally "push" excess downhill, "relabeling" stuck vertices. With the highest-label rule it hits O(V²√E) and is usually the fastest in practice on large dense graphs, though Dinic is simpler.

MPM (Malhotra-Pramodh-Kumar-Maheshwari). Finds a blocking flow in O(V²) by repeatedly saturating the minimum-throughput vertex, yielding O(V³) overall — competitive with Dinic on dense graphs and a clean alternative blocking-flow subroutine.

Common bugs and edge cases

• Forgetting reverse edges. Every forward edge needs a paired 0-capacity back edge so flow can be cancelled. Without it the algorithm finds suboptimal flows and never discovers the true minimum cut.
• Resetting the current-arc pointer per path. iter[] must persist across all augmentations within a phase and only reset after each BFS. Reset it per DFS call and the complexity collapses.
• Not pruning dead ends. When dfs returns 0 for a vertex, the advancing iterator effectively removes it from the level graph for the rest of the phase. Skip this and you re-walk dead subtrees endlessly.
• Integer overflow on the initial push. Seeding the DFS with Infinity (or a sum-of-capacities upper bound) is fine, but in C++ use a 64-bit type for the flow accumulator when capacities are large.
• Undirected edges done wrong. An undirected edge with capacity c is two directed edges each with capacity c (not one with a 0-cap reverse). Model it as a pair, both saturable.
• Reading the min-cut. After the final BFS, the set of vertices still reachable from s in the residual graph is the source side of the minimum cut. The cut edges are the saturated forward edges crossing that boundary — a frequent off-by-one source when reconstructing the cut.