ADVANCED ALGORITHMS - NETWORK FLOW:Dinic's Algorithm — O(V²E) Blocking Flows
Mastering dinic's algorithm — o(v²e) blocking flows concepts and implementation.
Dinic's Algorithm — O(V²E) Blocking Flows
Motivation
Edmonds-Karp runs in O(VE²). For dense graphs (E = O(V²)), this is O(V⁵). Dinic's algorithm improves this to O(V²E) and achieves O(E√V) for unit-capacity networks — critical for bipartite matching.
Level Graph and Blocking Flows
Level graph Lf: BFS from source in residual graph Gf. The level of a node is its BFS distance from s. Include only edges (u, v) in Gf where level(v) = level(u) + 1.
A blocking flow saturates at least one edge on every path from s to t in the level graph.
Key theorem: After augmenting via a blocking flow, the shortest s-t path distance in Gf strictly increases. This can happen at most O(V) times → O(V) phases.
Dinic's Algorithm
from collections import deque
class MaxFlowDinics:
"""
Dinic's algorithm: O(V^2 * E), O(E * sqrt(V)) for unit capacities.
Uses adjacency list with edge indices for O(E) blocking flow per phase.
"""
def __init__(self, n):
self.n = n
self.graph = [[] for _ in range(n)] # graph[u] = list of edge indices
self.edges = [] # (to, rev_idx, cap)
def add_edge(self, u, v, cap):
self.graph[u].append(len(self.edges))
self.edges.append([v, len(self.edges) + 1, cap]) # [to, rev, cap]
self.graph[v].append(len(self.edges))
self.edges.append([u, len(self.edges) - 1, 0]) # reverse edge
def bfs_level(self, s, t):
"""BFS to assign levels. Returns True if t is reachable."""
self.level = [-1] * self.n
self.level[s] = 0
queue = deque([s])
while queue:
u = queue.popleft()
for eid in self.graph[u]:
v, _, cap = self.edges[eid]
if cap > 0 and self.level[v] < 0:
self.level[v] = self.level[u] + 1
queue.append(v)
return self.level[t] >= 0
def dfs_blocking(self, u, t, pushed, iter_):
"""DFS to find blocking flow. iter_ tracks current edge to avoid re-traversal."""
if u == t:
return pushed
while iter_[u] < len(self.graph[u]):
eid = self.graph[u][iter_[u]]
v, rev, cap = self.edges[eid]
if cap > 0 and self.level[v] == self.level[u] + 1:
d = self.dfs_blocking(v, t, min(pushed, cap), iter_)
if d > 0:
self.edges[eid][2] -= d # Reduce forward capacity
self.edges[rev][2] += d # Increase backward capacity
return d
iter_[u] += 1
return 0
def max_flow(self, s, t):
flow = 0
while self.bfs_level(s, t): # O(V) phases
iter_ = [0] * self.n
while True: # Multiple DFS until blocking flow found
f = self.dfs_blocking(s, t, float('inf'), iter_)
if f == 0:
break
flow += f
return flow
# Example
g = MaxFlowDinics(4)
g.add_edge(0, 1, 10)
g.add_edge(0, 2, 10)
g.add_edge(1, 3, 10)
g.add_edge(2, 3, 10)
g.add_edge(1, 2, 1)
print(g.max_flow(0, 3)) # 20
Performance Analysis
- BFS phase: O(E) per phase, O(V) phases → O(VE) for all phases
- Blocking flow per phase: O(VE) in total across all DFS calls (with the "iter" pointer trick)
- Total: O(V²E)
For unit-capacity networks: O(E · √V) — this is why Dinic's is the algorithm of choice for bipartite matching via max-flow.
Comparison of Max-Flow Algorithms
| Algorithm | Time Complexity | Best For |
|---|---|---|
| Ford-Fulkerson (DFS) | O(E · max_flow) | Integer capacities, small flows |
| Edmonds-Karp (BFS) | O(VE²) | General graphs |
| Dinic's | O(V²E) | Dense graphs, general use |
| Dinic's (unit cap) | O(E√V) | Bipartite matching, unit graphs |
| Push-Relabel | O(V²√E) | Large dense graphs |
| HLPPS (highest-label) | O(V²√E) | Practical fastest in many benchmarks |
Practice Problems
- Implement Dinic's and verify against Edmonds-Karp on the same graph
- Use Dinic's to solve maximum bipartite matching in O(E√V)
- Given a network with unit capacities, find max flow and verify O(E√V) bound
- Add an edge to an existing max-flow solution without recomputing from scratch (incremental max-flow)