Dinic's Algorithm

Imagine water flowing through a network of pipes. Each pipe has a limited capacity, and you want to pump as much water as possible from a source to a sink. This is the maximum-flow problem, and it sits at the heart of logistics, chip design, image segmentation, and a dozen other fields.

The earliest algorithms — Ford–Fulkerson (1956) and Edmonds–Karp (1972) — found augmenting paths one at a time. They work, but they can be slow: Ford–Fulkerson can take a number of steps proportional to the total flow value, which may be enormous.

In 1970, a Soviet undergraduate named Yefim Dinic published a two-stage idea that changed everything. Instead of hunting for one path at a time, his algorithm first layers the entire graph with a BFS (producing a level graph where every edge strictly goes one level deeper), then floods that level graph all at once with a single blocking flow pass. Repeat until no more layering is possible — and the maximum flow is in hand.

The result: a provably $O(V^2 E)$ algorithm, where V is the number of vertices and E the number of edges. In practice it is often much faster, and on unit-capacity graphs it drops to a remarkable $O(E\sqrt{V})$. It remains one of the most elegant examples of "structure the problem first, then solve" in all of algorithmics — a principle you will also meet in P vs NP when researchers study what makes problems tractable.

Below is a small flow network. Source is node 0, Sink is node 5. Each edge shows its capacity. Click Run BFS Phase to build the level graph (nodes colour by depth), then Push Blocking Flow to saturate every shortest path in one DFS sweep, and finally Run Full Dinic to watch the entire algorithm converge to the maximum flow.

<p class="hint">{{hint}}</p>
<div id="canvas-wrap"><canvas id="canvas" width="560" height="300"></canvas></div>
<div class="status" id="status">{{press_to_begin}}</div>
<div class="btns">
  <button id="bfs" type="button">{{btn_bfs}}</button>
  <button id="dfs" type="button">{{btn_dfs}}</button>
  <button id="full" type="button">{{btn_full}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div id="info"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
#canvas-wrap { overflow-x: auto; }
canvas { display: block; max-width: 100%; background: #f4f7fa; border-radius: 10px; border: 1px solid #d0dae3; }
.status { font-size: 1rem; font-weight: 600; margin: .55rem 0 .3rem; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.info { color: #1d4e89; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .45rem; flex-wrap: wrap; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
#info { font-size: .82rem; color: #555; margin-top: .5rem; line-height: 1.6; min-height: 1.4em; }

// Code not found

Notice the two-phase rhythm: BFS assigns levels so that flow can only travel "downhill" (source → sink gets one level closer each step). The DFS then pushes as much flow as possible along every shortest path simultaneously — the blocking flow. After each round the shortest-path distance from source to sink strictly increases, so after at most $V-1$ rounds the algorithm terminates with the true maximum flow.

Why is Dinic's algorithm fast? The key is the level graph invariant.

• BFS layering (O(E) per phase): a BFS from the source assigns each node a level (its shortest-path distance). Only edges that go from level $\ell$ to level $\ell+1$ enter the level graph. This takes O(E) time.
• Blocking flow (O(VE) per phase): a DFS saturates every shortest augmenting path. Because the DFS advances only along level-graph edges and retreats (and removes dead-end edges) when stuck, each edge is visited at most twice — giving O(VE) per phase.
• Number of phases is O(V): after each blocking flow, the shortest-path distance from source to sink strictly increases by at least 1. Since that distance is at most $V-1$, there are at most $V-1$ phases.
• Total: $O(V) \times O(VE) = O(V^2 E)$. This was a major advance over Edmonds–Karp's $O(VE^2)$.

Bonus for unit graphs. When every edge capacity is 1 (or bounded by a constant), the number of phases drops to $O(\sqrt{E})$, yielding total time $O(E\sqrt{E}) = O(E^{3/2})$ — or $O(E\sqrt{V})$ on sparse graphs. This makes Dinic the algorithm of choice for bipartite matching and many combinatorial problems.

Dinic's result is proven and exact — not an open question like P vs NP. His 1970 paper (published in Soviet journals and later widely translated) closed the question of how fast max-flow could be done with the tools available then, and sparked decades of follow-up: the push-relabel algorithm (Goldberg–Tarjan, 1988) achieves $O(V^2\sqrt{E})$ on general graphs, but Dinic's blocking-flow structure remains the cleanest route to understand why max-flow is polynomially solvable.

Maximum flow is one of the most reused subroutines in all of computing, and Dinic's algorithm is the standard workhorse:

• Network routing: traffic engineering in backbone internet routers computes max-flow to decide how to split packets across links without exceeding link capacities.
• Bipartite matching: finding the largest matching in a bipartite graph reduces to max-flow on a unit-capacity network. Dinic's O(E√V) bound for unit graphs means it handles millions of edges in seconds — used in job-scheduling and ride-sharing assignments.
• Image segmentation (s-t cuts): the max-flow min-cut theorem says the maximum flow equals the minimum cut. Computer vision uses this to separate foreground from background in an image by finding the cheapest set of pixel-boundary edges to sever.
• Supply-chain and logistics: rail or road networks modelled as capacitated graphs use Dinic to find bottlenecks and plan capacity upgrades.
• Compiler register allocation: interference graphs in compilers are sometimes handled with flow-based methods that invoke Dinic internally.

The unifying theme: any time you need to push as much "stuff" as possible through a network with limited edges, you are looking at a max-flow problem — and Dinic's two-phase loop is almost certainly the algorithm quietly doing the work.

Dinic's algorithm is a masterclass in "structure before search." Instead of blindly hunting for augmenting paths, it first imposes a clean layered order on the graph, then exploits that order to saturate all shortest paths at once. The result — $O(V^2 E)$, or $O(E\sqrt{V})$ on unit graphs — transformed network flow from a theoretical curiosity into a practical tool used billions of times a day.

The deeper lesson is one you will find throughout complexity theory: the right structural decomposition often does more work than clever search ever could. That same spirit drives the level hierarchies in P vs NP research and the layered proofs behind problems like max matching. Dinic gave us not just an algorithm, but a blueprint for how to think about flow.