Dinic's Algorithm for Maximum Flow

Why Plain Edmonds-Karp Runs Out of Steam

Edmonds-Karp is the textbook fix to Ford-Fulkerson's nondeterminism: instead of picking any augmenting path, always use breadth-first search to find a shortest augmenting path in terms of edge count. This guarantees termination and a provable O(V times E squared) bound, but the algorithm still treats every single augmenting path as an isolated event. After pushing flow along one path, the entire BFS tree is discarded, and the next iteration searches the residual graph again from a blank slate, even though most of the graph's structure has not changed at all. On graphs with many parallel near-shortest paths, this means recomputing very similar breadth-first searches over and over, paying the full O(E) traversal cost for each individual path found. The wasted work is not in finding paths incorrectly, it is in forgetting everything learned after finding just one. Dinic's insight was that a single BFS pass already reveals the shortest-path distance from the source to every node, and that information stays valid for pushing flow along many paths, not just one, as long as those paths respect the same layering. Rather than one augmenting path per BFS, Dinic's algorithm extracts an entire maximal bundle of augmenting paths, called a blocking flow, from a single level graph before ever running BFS again. A blocking flow is a flow assignment such that every source-to-sink path in the level graph has at least one saturated edge, meaning no further flow can be pushed through the level graph without exceeding some edge's capacity. Finding this blocking flow still requires searching, but it can be done with one depth-first traversal augmented by pointer bookkeeping, rather than one traversal per path. The net effect is that the expensive breadth-first rebuild happens only O(V) times total across the whole algorithm, instead of once per augmenting path, and this restructuring is what separates Dinic's algorithm's complexity from Edmonds-Karp's.

Building the Level Graph with Breadth-First Search

Each phase of Dinic's algorithm begins with a genuine breadth-first search launched from the source node across the current residual graph, the graph formed by every edge that still has leftover capacity after accounting for flow already pushed along it and its reverse. The BFS assigns each reachable node a level number equal to the minimum number of residual edges needed to reach it from the source, exactly the same quantity a standard shortest-path BFS would compute. Only edges that move from level L to level L+1 are kept in the level graph; any residual edge connecting nodes at the same level, or pointing backward to a lower level, is discarded even if it has spare capacity. This pruning is essential and is what keeps the subsequent depth-first search efficient, because it guarantees every path found in the level graph is automatically a shortest path in the residual graph, and it prevents the DFS from wasting time wandering into dead ends or cycles. If the BFS completes without ever reaching the sink node, that is the algorithm's termination signal: no augmenting path exists anywhere in the residual graph, the level graph is empty of use, and the current flow is already the maximum flow, by the max-flow min-cut theorem. Constructing the level graph costs O(E) time and O(V) time for the traversal itself, since BFS visits each node once and examines each edge at most once. It is worth emphasizing that the level graph is a directed acyclic graph by construction, since edges strictly increase level, and this acyclic property is precisely why the DFS phase that follows can safely use single-pass pointer bookkeeping without ever revisiting a fully explored dead branch more than once. Every time this BFS step runs, the shortest distance from source to sink measured over the residual graph is guaranteed to have increased from the previous phase, a fact that underlies the whole complexity proof for the algorithm.

Finding a Blocking Flow with Depth-First Search

With the level graph fixed for this phase, Dinic's algorithm switches to a depth-first search whose job is to find a blocking flow, a maximal set of augmenting paths through the level graph such that no additional unit of flow can be routed through it afterward. The DFS starts at the source and greedily walks forward along level-graph edges, always advancing to the next level, until it either reaches the sink, in which case it pushes flow equal to the bottleneck capacity along the discovered path, or it hits a dead end with no viable forward edge, in which case it backtracks. The key efficiency trick is maintaining, for every node, a current-edge pointer or iterator index into that node's adjacency list. Once an edge has been fully saturated, or once the search determines that a node cannot reach the sink at all, that pointer is advanced past the exhausted edge and never reconsidered again during this phase. This means each edge in the level graph is examined and discarded at most once per phase, not once per augmenting path, so the entire blocking-flow search across all paths in one phase costs only O(V times E) in the worst case, since each of the up to O(V) augmenting paths found can require O(V) edges to traverse, and pointer advancement amortizes the edge-scanning cost. This single DFS pass, pushing flow along multiple paths without restarting, is the mechanical heart of Dinic's speed advantage. When the DFS can no longer reach the sink from the source at all using unsaturated level-graph edges, the blocking flow for this phase is complete. Some nodes may become permanently dead-ended partway through this process, and marking them so the DFS never revisits them is another important bookkeeping optimization that keeps the search from repeating fruitless exploration.

Alternating Phases and the Termination Guarantee

Once a phase's blocking flow is fully saturated, the algorithm discards the current level graph entirely and returns to breadth-first search, rebuilding a brand-new level graph from scratch based on the residual capacities left behind by the flow just pushed. This alternation, BFS to build structure, DFS to exploit it fully, BFS again to rebuild, is repeated until a phase's BFS fails to reach the sink at all, at which point the algorithm halts and the accumulated flow is provably maximum. The correctness argument rests on a classical lemma: the shortest-path distance from source to sink in the residual graph is non-decreasing across phases, and in fact strictly increases after every single blocking-flow phase. Intuitively, once a phase saturates every shortest path of a given length, any remaining augmenting route in the residual graph must take a longer route, since all the short ones have at least one bottleneck edge. Because the shortest-path distance is bounded above by the number of vertices, and it strictly increases by at least one after each phase, there can be at most O(V) phases in total before the distance would need to exceed V, which is impossible, forcing termination. This is a much stronger termination guarantee than Edmonds-Karp offers implicitly, since Edmonds-Karp bounds the number of augmenting paths directly at O(V times E) rather than bounding the number of phases, where each phase in Dinic's algorithm handles potentially many paths at once. Multiplying the O(V) phase bound by the O(E) cost of each phase's BFS-plus-blocking-flow work yields the overall O(V squared times E) time complexity, and on dense or highly connected graphs this can be a dramatic practical improvement, especially since many real-world flow networks exhibit far fewer than the worst-case number of phases in practice.

Where Dinic's Algorithm Fits Among Max Flow Methods

Dinic's algorithm sits in a family of maximum flow techniques that trace back to the Ford-Fulkerson method, the general framework of repeatedly finding augmenting paths in a residual graph until none remain. Plain Ford-Fulkerson using arbitrary path selection, such as depth-first search without any layering discipline, can degrade badly on graphs with irrational or poorly chosen capacities, sometimes even failing to terminate in pathological integer-capacity cases if implemented carelessly. Edmonds-Karp fixes termination by insisting on shortest augmenting paths but pays for that guarantee with repeated full-graph searches. Dinic's algorithm keeps the shortest-path discipline that makes Edmonds-Karp correct while amortizing the search cost across many paths per phase, which is why its complexity strictly improves on Edmonds-Karp for general graphs. It is worth noting that on unit-capacity graphs, such as those arising from bipartite matching problems, Dinic's algorithm achieves an even better bound of O(E times square root of V), which is part of why it underlies efficient bipartite matching algorithms like Hopcroft-Karp in spirit. Later refinements pushed max flow theory further still, including link-cut tree implementations that achieve O(V times E times log V) and, much more recently, near-linear time algorithms for max flow on general graphs discovered in the 2020s. Even so, Dinic's algorithm remains a staple in competitive programming and a common baseline in production systems because its two-phase structure, BFS layering followed by DFS blocking flow, is conceptually clean, reasonably simple to implement correctly, and fast enough in practice for the vast majority of flow networks encountered outside of extreme theoretical worst cases. Studying it closely also builds strong intuition for how layered graph structures and amortized pointer bookkeeping can turn a naive quadratic-feeling repeated search into a provably tighter bound.

Frequently asked questions

Try it live

Everything above runs in your browser — open Dinic's Algorithm for Maximum Flow and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.