Dinic's Algorithm

Imagine you're shipping packages and you've found every possible shortest route from the warehouse to the delivery hub. Edmonds-Karp sends packages along one route, then re-checks everything. Dinic's says: send packages along ALL shortest routes simultaneously, then re-evaluate. That's the entire idea.

This batch approach — called a blocking flow — makes Dinic's dramatically faster in practice and provably better in theory.

Phase 1: Build the Level Graph (BFS)

Start each phase with a BFS from the source s through the residual graph. Assign each vertex a level = its distance from s in number of edges.

The level graph keeps only edges (u→v) where level[v] = level[u] + 1 — edges that strictly move toward the sink. All s-t paths in the level graph have the same minimum length. If the sink t is unreachable, the algorithm stops (max flow found).

Phase 2: Find a Blocking Flow (DFS)

A blocking flow is a flow in the level graph where every s-t path has at least one saturated edge. After sending a blocking flow, no s-t path remains in the level graph — forcing the next BFS to find longer paths.

Finding the blocking flow uses DFS with a "dead end" optimization: when you reach a dead end (no forward edges left), delete that vertex from the level graph so you never try it again. When you reach t, send flow back along the path, saturating the bottleneck edge. Each edge is deleted at most once, so the whole blocking flow phase costs \(O(VE)\).

Why Path Lengths Increase Each Phase

After a blocking flow, every s-t path in the current level graph is broken. The next BFS must find a strictly longer shortest path. Since path lengths are at most V-1, there can be at most \(O(V)\) phases.

Each phase: one BFS = \(O(E)\), one blocking flow = \(O(VE)\). Total: \(O(V)\) × \(O(VE)\) = \(O(V^2E)\).

Unit Capacity Networks and Bipartite Matching

When all capacities are 1, blocking flows saturate edges very quickly and path lengths grow faster. The number of phases drops to \(O(√E)\) in general and \(O(√V)\) for bipartite graphs. Total complexity: \(O(E√V)\) — the same bound achieved by the Hopcroft-Karp matching algorithm (which is essentially Dinic's applied to bipartite graphs).

Dinic's Algorithm

from collections import deque

class Dinic:
    def __init__(self, n):
        self.n   = n
        self.adj = [[] for _ in range(n)]  # [to, rev_idx, cap]

    def add_edge(self, u, v, cap):
        self.adj[u].append([v, len(self.adj[v]), cap])
        self.adj[v].append([u, len(self.adj[u])-1, 0])  # backward 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.adj[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, pushed):
        if u == t: return pushed
        while self.it[u] < len(self.adj[u]):
            v, rev, cap = self.adj[u][self.it[u]]
            if cap > 0 and self.level[v] == self.level[u] + 1:
                d = self.dfs(v, t, min(pushed, cap))
                if d > 0:
                    self.adj[u][self.it[u]][2] -= d
                    self.adj[v][rev][2]         += d
                    return d
            self.it[u] += 1
        return 0

    def max_flow(self, s, t):
        flow = 0
        while self.bfs(s, t):
            self.it = [0] * self.n
            while True:
                f = self.dfs(s, t, float('inf'))
                if f == 0: break
                flow += f
        return flow

d = Dinic(6)
d.add_edge(0,1,10); d.add_edge(0,2,10)
d.add_edge(1,3,5);  d.add_edge(2,4,10)
d.add_edge(3,5,10); d.add_edge(4,5,10)
d.add_edge(1,4,5)
print(d.max_flow(0, 5))  # 15

Output

Complexity

🌐 General graphs\(O(V)\) phases × \(O(VE)\) blocking flow; wins over \(O(VE^2)\) when the graph is sparse

Better than Edmonds-Karp for sparse graphs\(O(V^2E)\)

⚡ Unit capacity networksPath lengths increase rapidly; only \(O(√V)\) phases needed for bipartite and unit graphs

Near-linear phases\(O(E√V)\)

👥 Bipartite matchingDinic's on a unit-capacity bipartite flow network matches Hopcroft-Karp's bound exactly

Same as Hopcroft-Karp\(O(E√V)\)

🔍 Each blocking flow phaseEach edge deleted at most once per phase; dead-end vertices pruned in \(O(1)\) amortized

Linear with dead-end pruning\(O(VE)\)

Phase 1: Build the Level Graph (BFS)

Phase 2: Find a Blocking Flow (DFS)

Why Path Lengths Increase Each Phase

Unit Capacity Networks and Bipartite Matching

Dinic's Algorithm

Complexity

Quick check