Wait, What?
Max-flow becomes much easier to reason about when you stop chasing one augmenting path at a time and instead organise the residual network into phases.
Dinic’s algorithm is a powerful next step after Ford–Fulkerson and Edmonds–Karp. It teaches a professional habit that appears across algorithm design: build structure first, then exploit that structure aggressively before rebuilding it. In Dinic, a breadth-first search builds a level graph, then a depth-first search pushes a blocking flow through that level graph until every source-to-sink route in the current phase is blocked.
Quick Answer
Learn Dinic in this order: flow constraints → residual edges → shortest residual distance → level graph → blocking flow → current-arc optimization → phase progress → complexity → implementation testing. The algorithm is not “BFS plus DFS” by coincidence. BFS creates an acyclic layered problem; DFS exhausts that layered problem before the next BFS is allowed to change the geometry.
1. Begin With the Max-Flow Contract
A flow network is a directed graph with a source s, a sink t, and a non-negative capacity on each edge. A valid flow obeys two rules: it never exceeds capacity, and every intermediate vertex sends out exactly as much flow as it receives. The goal is to maximize the total flow leaving the source and entering the sink.
Before learning Dinic, make sure you can answer three questions without code: What capacity remains on a forward edge? Why does a reverse residual edge exist? What does it mean for the sink to become unreachable in the residual graph? These are the load-bearing ideas.
2. Residual Edges Are the Correction Mechanism
If an edge u→v has capacity 7 and currently carries 4 units of flow, its forward residual capacity is 3. The reverse residual edge v→u has residual capacity 4 because up to four units of previous flow can be cancelled or redirected later.
This is why max-flow algorithms are not merely “send as much as possible.” A locally sensible early decision may need to be revised. The residual network is the bookkeeping system that makes those revisions legal.
3. What Dinic Changes
Ford–Fulkerson repeatedly finds any augmenting path. Edmonds–Karp chooses a shortest augmenting path using BFS. Dinic goes further: one BFS identifies all residual vertices by shortest distance from the source, and the algorithm then pushes flow only along edges that move exactly one level forward.
That restriction creates the level graph. An edge u→v belongs to the current level graph only when it has positive residual capacity and level[v] = level[u] + 1. Because every accepted edge moves to a larger level, the level graph is acyclic.
4. Work a Tiny Level Graph by Hand
Suppose the residual network has source S, sink T, and paths S→A→T and S→B→C→T. BFS gives levels S=0, A=1, B=1, T=2 through A, and C=2. The edge C→T would move from level 2 to level 2 and therefore is not part of the current level graph. In this phase, Dinic is interested only in the shortest residual geometry.
After the short route is saturated, a later BFS may assign T a larger level and bring the longer route into play. This is the central progress measure: after a blocking flow, the shortest residual distance from s to t strictly increases whenever t remains reachable.
5. Blocking Flow Is More Than One Augmenting Path
A blocking flow in a level graph is a flow that blocks every s→t path in that level graph: every such path contains at least one saturated edge. Dinic does not need to compute a mathematically maximum flow inside the level graph. It only needs enough flow to make every current shortest route unusable.
That distinction is important. The phase ends because the current layered geometry has been exhausted, not because the whole network is solved.
6. The Core Algorithm
flow = 0
while BFS_build_levels(s, t):
reset current-edge pointers
while True:
pushed = DFS_blocking_flow(s, INF)
if pushed == 0:
break
flow += pushed
return flowThe BFS ignores zero-capacity residual edges. The DFS follows only admissible level edges. When flow is pushed through an edge, its forward residual capacity decreases and the reverse residual capacity increases by the same amount.
7. Why the DFS Needs a Current-Arc Pointer
A naive DFS can revisit the same dead edge many times. Dinic implementations therefore keep a pointer such as ptr[v] or next_edge[v] recording which outgoing edge should be tried next from each vertex during the current phase.
Once an edge has been shown unable to push additional flow in the present level graph, earlier edges do not need to be reconsidered. The pointer only moves forward until the next BFS rebuilds the levels. This small implementation detail is one of the main reasons practical Dinic code is fast.
8. A Clean Python Reference Implementation
from collections import deque
class Dinic:
def __init__(self, n):
self.n = n
self.g = [[] for _ in range(n)]
def add_edge(self, u, v, cap):
fwd = [v, cap, None]
rev = [u, 0, fwd]
fwd[2] = rev
self.g[u].append(fwd)
self.g[v].append(rev)
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, rev in self.g[u]:
if cap > 0 and self.level[v] == -1:
self.level[v] = self.level[u] + 1
q.append(v)
return self.level[t] != -1
def dfs(self, u, t, pushed):
if pushed == 0:
return 0
if u == t:
return pushed
while self.ptr[u] 0 and self.level[v] == self.level[u] + 1:
take = self.dfs(v, t, min(pushed, cap))
if take:
e[1] -= take
rev[1] += take
return take
self.ptr[u] += 1
return 0
def max_flow(self, s, t):
total = 0
INF = 10**30
while self.bfs(s, t):
self.ptr = [0] * self.n
while True:
pushed = self.dfs(s, t, INF)
if pushed == 0:
break
total += pushed
return totalThis version emphasizes the invariant rather than micro-optimisation. Production code may use compact edge objects, integer indices into a flat edge array, iterative DFS to avoid recursion depth, or capacity types wider than ordinary integers.
9. The Correctness Story
There are two layers to the proof. First, every augmentation respects capacity and flow conservation because forward and reverse residual capacities are updated symmetrically. Second, once a blocking flow is found, no s→t path of the current shortest length remains. Therefore, if the sink is still reachable after the phase, its BFS level must be larger.
The sink can have level at most V−1 in a simple shortest path, so there are fewer than V successful phases. When BFS can no longer reach the sink, there is no augmenting path in the residual graph. By the max-flow/min-cut theorem, the current flow is maximum.
10. Complexity: Know the General Bound and the Structure-Sensitive Improvements
For a general network, the standard bound is O(V²E). A blocking-flow phase can be implemented in O(VE), and there are fewer than V phases. Special graph classes admit stronger bounds. For unit networks, Dinic can achieve O(E√V). For unit-capacity graphs, other useful bounds include O(E√E) and O(EV2/3), depending on the analysis regime.
Professional use should not stop at an asymptotic label. Measure the number of vertices, edges, capacity magnitudes, graph density, recursion behaviour and memory traffic. A theoretically strong flow algorithm can still lose to a simpler implementation on small instances.
11. Build Tests Around Invariants, Not Just Final Answers
- Every residual capacity must remain non-negative.
- For every original edge, forward residual plus current flow should equal original capacity.
- Every intermediate vertex must conserve flow.
- Every DFS step in a phase must move from level i to level i+1.
- After a completed blocking-flow phase, a fresh BFS must either fail to reach t or give t a strictly larger level.
- For small random graphs, compare the result with a trusted max-flow implementation.
12. Common Failure States
- Forgetting the reverse residual edge.
- Updating only the forward residual capacity after a push.
- Allowing DFS to follow an edge that does not advance exactly one level.
- Failing to reset current-arc pointers after each new BFS.
- Resetting pointers too often and losing the performance benefit.
- Using a capacity type that can overflow when totals are accumulated.
- Treating the blocking flow as a single path rather than exhausting the current level graph.
- Assuming the O(V²E) bound predicts real runtime on every graph family.
13. From Beginner to Professional
Beginner: draw residual edges by hand and trace one augmentation. Foundation: construct a level graph from a residual network. Intermediate: implement blocking-flow DFS and current arcs. Advanced: prove phase progress and derive the O(V²E) bound. Professional: benchmark Dinic against Edmonds–Karp and push–relabel on sparse, dense, unit-capacity and adversarial networks; inspect cache behaviour and choose a representation appropriate to the workload.
14. When Dinic Is the Right Tool
Dinic is an excellent general-purpose choice for many contest, teaching and moderate-scale engineering flow problems. It is especially attractive when the graph is sparse or has unit-like structure, and it maps naturally to bipartite matching via a flow reduction. For very large industrial instances, specialized push–relabel, cost-scaling, network-simplex or domain-specific solvers may be preferable depending on the actual optimisation problem.
Learning Hall Boundary
This article owns Dinic’s phased max-flow method: level graphs, blocking flows, current arcs, correctness and implementation practice. It does not replace the existing Learning Hall network-flow foundations, max-flow/min-cut theorem, bipartite matching or general graph-algorithm articles. Those remain the prerequisite and neighbouring canonical jobs.
Evidence Boundary
Dinic’s algorithm was introduced by Yefim Dinitz in 1970. The current algorithmic description and standard O(V²E) bound are consistent with modern references including Algorithms for Competitive Programming and university max-flow teaching materials from Princeton. The teaching sequence here also follows current computing-education guidance that emphasizes code reading, complexity, testing and debugging, while using worked examples and explicit subgoals to reduce unnecessary cognitive load.
Professional rule: if you cannot explain why a completed blocking flow forces the next shortest residual s→t path to become longer, you can run Dinic’s code, but you do not yet understand Dinic’s algorithm.
eduKate Sengkang 