Dinic's Algorithm

Dinic's algorithm (also known as Dinitz's algorithm) is a strongly polynomial algorithm in computation and algorithms that computes a maximum s–t flow in a directed capacitated flow network G = (V, E, c) in O(V²E) worst-case time. Developed in 1969 and published in 1970 by Soviet computer scientist Yefim Dinitz (transliterated as E. A. Dinic in early English translations), the algorithm was discovered independently of and prior to the O(V E²) Edmonds–Karp specialization of the Ford–Fulkerson algorithm.

Rather than searching the residual network G_f from scratch for a single shortest augmenting path at a time, Dinic's algorithm operates in phases. In each phase, a Breadth-First Search (BFS) partitions the residual network into a level graph G_L containing all shortest s–t augmenting paths simultaneously, and a subsequent Depth-First Search (DFS) with current-arc pointer maintenance pushes a blocking flow that saturates at least one edge along every s–t path in G_L. On unit-capacity networks, its complexity improves to O(E min(V^2/3, E^1/2)), and on bipartite matching networks it runs in O(E √V) time, matching the Hopcroft–Karp algorithm.

Residual Network and Level Graph Partitioning

Let G = (V, E, c) be a directed network with source s ∈ V, sink t ∈ V, vertex count V = |V|, and edge count E = |E|. Given a feasible s–t flow f, the residual network G_f = (V, E_f) consists of all directed pairs (u, v) with positive residual capacity c_f(u, v) = c(u, v) − f(u, v) + f(v, u) > 0.

At the start of each phase, Dinic's algorithm computes for every vertex v ∈ V its unweighted shortest-path distance (or level) d_f(v) from the source s in G_f using a single BFS traversal in O(E) time, setting d_f(s) = 0 and d_f(v) = ∞ if v is unreachable from s. The level graph G_L = (V, E_L) is the directed acyclic subgraph of G_f containing only edges that advance the distance label by unit increments:

Every directed path from s to t in G_L has length d_f(t) and is therefore a shortest s–t augmenting path in G_f. Conversely, any residual edge (u, v) ∈ E_f with d_f(v) ≤ d_f(u) cannot belong to any shortest s–t path during the current phase and is omitted from G_L.

Blocking Flows vs. Maximum Flows

A flow g in the level graph G_L is called a blocking flow (or maximal flow) if every directed path from s to t in G_L contains at least one saturated edge (u, v) where g(u, v) = c_f(u, v). Every maximum flow in G_L is a blocking flow, but a blocking flow need not be a maximum flow in G_L because blocking flows are found greedily without using backward cancellation edges within the same phase.

Strict Monotonicity of Sink Distance Across Phases

The foundational correctness and termination invariant of Dinic's algorithm is the Distance Monotonicity Lemma: if f′ = f + g is the flow obtained by augmenting f with a blocking flow g in G_L, then the shortest-path distance from s to t in the new residual network G_f′ increases by at least 1:

Proof Sketch: Every edge (u, v) ∈ E_f′ is either an unsaturated residual edge that already belonged to E_f (satisfying d_f(v) ≤ d_f(u) + 1) or the reverse (v, u) of an edge (u, v) ∈ E_L along which g pushed positive flow (where d_f(u) = d_f(v) − 1, so it still satisfies d_f(u) ≤ d_f(v) + 1). Thus no path from s to t in G_f′ can have length less than d_f(t). Furthermore, any path of length d_f(t) in G_f′ would have to use only edges with d_f(v) = d_f(u) + 1, which belong exclusively to E_L; however, because g is a blocking flow in G_L, at least one edge on every such path was saturated by g and deleted from E_f′. Therefore, d_f′(t) > d_f(t). Because a simple s–t path contains at most V − 1 edges, Dinic's algorithm terminates in at most V − 1 phases.

Current-Arc Pointer Optimization (Shiloach–Even)

In Dinitz's original 1970 formulation and Shimon Even and Yossi Shiloach's 1975 refinement, each blocking-flow phase executes a Depth-First Search from s to t while maintaining for each vertex u ∈ V a current-arc pointer indexing its adjacency list in G_L:

1. DFS Advance: From vertex u, inspect the edge (u, v) currently indexed by u's pointer. If (u, v) ∈ E_L and c_f(u, v) > 0, recursively advance to v.
2. Dead-End Pruning and Pointer Increment: If the recursive call from v returns 0 pushed flow (meaning t is no longer reachable from v in the remaining unsaturated level graph) or if (u, v) becomes saturated, increment u's current-arc pointer to the next incident edge. Once an edge is bypassed by the pointer, it is never inspected again during the current phase.
3. Path Augmentation: Whenever t is reached, push bottleneck capacity Δ along the current DFS stack (or push multiple paths simultaneously via multiple-path DFS), saturating at least one bottleneck edge.

Because each DFS step either advances toward t (at most V steps before reaching t or hitting a dead end) or increments a vertex's current-arc pointer (which can happen at most E times across the entire phase), finding a blocking flow takes at most O(V E) time per phase. Multiplied across at most V − 1 phases, total worst-case complexity is O(V²E). Replacing the DFS stack with a link/cut tree (Sleator and Tarjan, 1983) reduces the blocking-flow phase to O(E log V) and overall max-flow complexity to O(V E log V).

Unit-Capacity Networks and Bipartite Matching Bounds

When edge capacities are restricted to integers in {0, 1}, Alexander Karzanov (1973) and Even and Tarjan (1975) proved much tighter bounds within computational complexity theory:

• Unit-Capacity Networks: In any network where c(e) = 1 for all e ∈ E, each DFS augmentation saturates every edge along its path, so finding a blocking flow takes O(E) time per phase. After k = ⌈min(V^2/3, E^1/2)⌉ phases, the distance from s to t exceeds k, and the pigeonhole principle implies the existence of a level boundary with residual capacity at most O(min(V^2/3, E^1/2)). Thus at most O(min(V^2/3, E^1/2)) additional phases occur, giving O(E min(V^2/3, E^1/2)) total time.
• Unit Networks (Bipartite Matching): If every internal vertex v ∈ V \ {s, t} additionally has either in-degree 1 or out-degree 1, all augmenting paths in a blocking flow are vertex-disjoint. After √V phases, the remaining residual flow is at most √V, yielding O(E √V) total time.

Comparative Complexity Across Maximum-Flow Variants

Dinic's algorithm is widely deployed as the core maximum-flow engine in Gomory–Hu tree construction, circulation with lower bounds, project selection (maximum-weight closure), and baseball elimination. In structural bioinformatics and systems biology, it computes minimum reaction cut sets in metabolic networks and resolves exon-splicing graph decompositions in transcriptomic assemblers.

Why is the current-arc pointer essential for the O(V²E) bound?

Without advancing and persisting the current-arc pointer at each vertex during a phase, a naive DFS could repeatedly traverse and backtrack across the same dead-end subgraphs in G_L, degrading a single blocking-flow phase from O(V E) to O(V²E) or worse.

How does Dinic's algorithm relate to the Hopcroft–Karp algorithm?

When applied to the standard unit-capacity source-to-sink network representing a bipartite graph G = (U ∪ W, E), Dinic's algorithm executes the exact same phase structure and achieves the same O(E √V) time bound as the Hopcroft–Karp algorithm.

1. Dinic, E. A. (1970). "Algorithm for solution of a problem of maximum flow in a network with power estimation." Soviet Mathematics Doklady, 11(5), 1277–1280. https://mathscinet.ams.org/mathscinet-getitem?mr=0287976
2. Even, S., & Tarjan, R. E. (1975). "Network flow and testing graph connectivity." SIAM Journal on Computing, 4(4), 507–518. https://doi.org/10.1137/0204043
3. Sleator, D. D., & Tarjan, R. E. (1983). "A data structure for dynamic trees." Journal of Computer and System Sciences, 26(3), 362–391. https://doi.org/10.1016/0022-0000(83)90006-590006-5)
4. Dinitz, Y. (2006). "Dinitz' algorithm: The original version and Even's version." In Theoretical Computer Science: Essays in Memory of Shimon Even (pp. 218–240). Springer. https://doi.org/10.1007/11685654_10