Dinic's Algorithm: Efficient Maximum Flow
Maximum flow problems appear everywhere in computing, often disguised as something else entirely. When you're routing packets through a network, you're solving a flow problem. When you're matching...
Key Insights
- Dinic’s algorithm achieves O(V²E) complexity by combining BFS-constructed level graphs with DFS-based blocking flows, making it significantly faster than Ford-Fulkerson’s O(VE²) for dense graphs.
- The current-arc optimization eliminates redundant edge traversal during DFS, providing substantial real-world speedups that are essential for competitive programming and production use.
- On unit-capacity networks like bipartite matching, Dinic’s runs in O(E√V), making it the go-to algorithm for matching problems where specialized algorithms aren’t available.
Introduction to Maximum Flow Problems
Maximum flow problems appear everywhere in computing, often disguised as something else entirely. When you’re routing packets through a network, you’re solving a flow problem. When you’re matching job candidates to positions, that’s flow. Image segmentation in computer vision? Also flow. Even baseball elimination—determining whether a team can still make the playoffs—reduces to maximum flow.
The core problem is deceptively simple: given a directed graph with edge capacities, find the maximum amount of “flow” you can push from a source node to a sink node without exceeding any edge’s capacity. The challenge lies in doing this efficiently. A naive approach might find augmenting paths one at a time, but this can be catastrophically slow on certain graph structures.
For any system handling real-time decisions—network traffic management, resource allocation, or recommendation systems—the difference between an O(VE²) algorithm and an O(V²E) algorithm can mean the difference between milliseconds and minutes.
From Ford-Fulkerson to Dinic’s: Evolution of Flow Algorithms
Ford-Fulkerson established the foundational approach: repeatedly find augmenting paths from source to sink, push flow along them, and update residual capacities. The problem? With arbitrary path selection, it can take O(E × max_flow) iterations, which becomes unbounded for irrational capacities and painfully slow for large integer capacities.
Edmonds-Karp improved this by always choosing the shortest augmenting path via BFS, guaranteeing O(VE) iterations and O(VE²) total complexity. Better, but still not great for dense graphs where E approaches V².
Dinic’s algorithm, published by Yefim Dinitz in 1970, takes a different approach. Instead of finding one augmenting path per iteration, it constructs a “level graph” using BFS and then finds all augmenting paths of that length simultaneously using DFS. This blocking flow approach guarantees the shortest path distance increases by at least one each phase, capping the number of phases at O(V) and yielding O(V²E) overall complexity.
Let’s start with a clean graph representation:
from collections import defaultdict, deque
from typing import List, Tuple
class FlowNetwork:
def __init__(self, n: int):
self.n = n
self.graph = defaultdict(list) # adjacency list: node -> [(to, capacity, rev_index)]
def add_edge(self, u: int, v: int, capacity: int):
# Forward edge
self.graph[u].append([v, capacity, len(self.graph[v])])
# Reverse edge (for residual graph)
self.graph[v].append([u, 0, len(self.graph[u]) - 1])
The key insight here is storing reverse edge indices. When we push flow along an edge, we need to update both the forward edge (decrease capacity) and the reverse edge (increase capacity to allow flow cancellation).
Core Concepts: Level Graphs and Blocking Flows
A level graph assigns each node a “level” equal to its BFS distance from the source. We only consider edges that go from level d to level d+1. This layered structure has a crucial property: every path from source to sink in the level graph is a shortest path in the original residual graph.
A blocking flow saturates at least one edge on every source-to-sink path in the level graph. Once we’ve found a blocking flow, no more augmenting paths of the current shortest length exist, forcing the shortest path distance to increase.
def bfs_level_graph(self, source: int, sink: int) -> bool:
"""Build level graph using BFS. Returns True if sink is reachable."""
self.level = [-1] * self.n
self.level[source] = 0
queue = deque([source])
while queue:
u = queue.popleft()
for v, cap, _ in self.graph[u]:
if cap > 0 and self.level[v] == -1:
self.level[v] = self.level[u] + 1
queue.append(v)
return self.level[sink] != -1
This BFS runs in O(E) and produces the level array that guides our DFS. We only traverse edges with positive residual capacity, naturally working on the residual graph.
The Algorithm: Step-by-Step Implementation
The main loop alternates between two phases: build the level graph with BFS, then find blocking flows with DFS. We repeat until the sink becomes unreachable.
class Dinic:
def __init__(self, n: int):
self.n = n
self.graph = [[] for _ in range(n)]
def add_edge(self, u: int, v: int, capacity: int):
self.graph[u].append([v, capacity, len(self.graph[v])])
self.graph[v].append([u, 0, len(self.graph[u]) - 1])
def bfs(self, source: int, sink: int) -> bool:
self.level = [-1] * self.n
self.level[source] = 0
queue = deque([source])
while queue:
u = queue.popleft()
for v, cap, _ in self.graph[u]:
if cap > 0 and self.level[v] == -1:
self.level[v] = self.level[u] + 1
queue.append(v)
return self.level[sink] != -1
def dfs(self, u: int, sink: int, pushed: int) -> int:
if u == sink:
return pushed
while self.iter[u] < len(self.graph[u]):
edge = self.graph[u][self.iter[u]]
v, cap, rev = edge
if cap > 0 and self.level[v] == self.level[u] + 1:
flow = self.dfs(v, sink, min(pushed, cap))
if flow > 0:
edge[1] -= flow
self.graph[v][rev][1] += flow
return flow
self.iter[u] += 1
return 0
def max_flow(self, source: int, sink: int) -> int:
flow = 0
while self.bfs(source, sink):
self.iter = [0] * self.n # Reset edge pointers
while True:
pushed = self.dfs(source, sink, float('inf'))
if pushed == 0:
break
flow += pushed
return flow
The iter array is the current-arc optimization—we’ll discuss it next. The DFS only follows edges that increase the level by exactly one, ensuring we stay within the level graph.
Optimizations and Edge Cases
The current-arc optimization (self.iter) is critical. Without it, each DFS call might re-examine edges we’ve already determined are useless for this phase. By maintaining a pointer to the “current” edge for each node and never backtracking, we ensure each edge is examined at most once per phase.
// C++ version with pointer optimization (often faster for competitive programming)
struct Dinic {
struct Edge { int to, cap, rev; };
vector<vector<Edge>> graph;
vector<int> level, iter;
int n;
Dinic(int n) : n(n), graph(n), level(n), iter(n) {}
void add_edge(int from, int to, int cap) {
graph[from].push_back({to, cap, (int)graph[to].size()});
graph[to].push_back({from, 0, (int)graph[from].size() - 1});
}
int dfs(int v, int t, int f) {
if (v == t) return f;
for (int& i = iter[v]; i < graph[v].size(); i++) {
Edge& e = graph[v][i];
if (e.cap > 0 && level[v] < level[e.to]) {
int d = dfs(e.to, t, min(f, e.cap));
if (d > 0) {
e.cap -= d;
graph[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
int max_flow(int s, int t) {
int flow = 0;
while (bfs(s, t)) {
fill(iter.begin(), iter.end(), 0);
int f;
while ((f = dfs(s, t, INT_MAX)) > 0)
flow += f;
}
return flow;
}
};
For bidirectional edges (where flow can go either direction), add two directed edges with the same capacity. The residual graph naturally handles this.
Practical Application: Bipartite Matching
Maximum bipartite matching is a classic application where Dinic’s shines. Connect a super-source to all left nodes, all right nodes to a super-sink, and edges between matchable pairs—all with capacity 1.
def max_bipartite_matching(left_size: int, right_size: int,
edges: List[Tuple[int, int]]) -> int:
"""
Find maximum matching in bipartite graph.
Left nodes: 0 to left_size-1
Right nodes: left_size to left_size+right_size-1
"""
n = left_size + right_size + 2
source = n - 2
sink = n - 1
dinic = Dinic(n)
# Source to all left nodes
for i in range(left_size):
dinic.add_edge(source, i, 1)
# All right nodes to sink
for i in range(right_size):
dinic.add_edge(left_size + i, sink, 1)
# Edges between left and right
for u, v in edges:
dinic.add_edge(u, left_size + v, 1)
return dinic.max_flow(source, sink)
# Example: 3 workers, 3 jobs, some compatibility edges
edges = [(0, 0), (0, 1), (1, 1), (1, 2), (2, 0)]
print(max_bipartite_matching(3, 3, edges)) # Output: 3
On unit-capacity networks, Dinic’s achieves O(E√V) complexity because the number of phases is bounded by O(√V). This makes it competitive with the Hopcroft-Karp algorithm specifically designed for bipartite matching.
Performance Benchmarks and When to Use Dinic’s
In practice, algorithm choice depends on graph structure:
| Algorithm | Complexity | Best For |
|---|---|---|
| Dinic’s | O(V²E) | General graphs, unit capacity |
| Push-Relabel | O(V²E) or O(V³) | Dense graphs |
| HLPP | O(V²√E) | Very dense graphs |
Dinic’s excels when:
- The graph has unit or small capacities (O(E√V) for unit capacity)
- You need a simple, correct implementation quickly
- The graph is relatively sparse
For production systems, consider libraries like Google OR-Tools or NetworkX (Python), or LEMON (C++). They offer optimized implementations with better constant factors than hand-rolled code.
However, understanding Dinic’s internals matters. When debugging flow-based systems or adapting the algorithm for specialized constraints (minimum-cost flow, flow with lower bounds), knowing how level graphs and blocking flows interact is invaluable.
The algorithm’s elegance lies in its guarantee of progress: each BFS phase strictly increases the shortest path length, and within each phase, the current-arc optimization ensures we never waste work. This combination of theoretical soundness and practical efficiency is why Dinic’s remains a cornerstone of flow algorithms fifty years after its invention.