Dinic's Algorithm Implementation
What you'll learn: How Dinic's algorithm efficiently computes maximum flow by building level graphs with BFS and finding blocking flows with DFS.
The Core Idea
Dinic's algorithm improves on simpler flow algorithms by being more selective about which augmenting paths to explore. Instead of randomly finding any path from source to sink, it works in phases:
- Build a level graph using BFS to assign each node a "distance" (level) from the source
- Find blocking flows using DFS, exploring only edges that move forward one level at a time
Think of it like organizing a relay race: BFS creates "stations" at each distance from start, and DFS finds multiple relay paths that only move forward through consecutive stations—never backward or skipping ahead.
Level Graph Construction
Use BFS from the source to assign levels. An edge (u, v) belongs in the level graph only if:
- It has residual capacity (capacity > 0)
level[v] = level[u] + 1(moves exactly one level forward)
This filtering ensures we only consider shortest paths in the residual network.
Blocking Flow with DFS
Run DFS on the level graph to push flow. A flow is "blocking" when every path from source to sink contains at least one saturated (fully used) edge. DFS naturally explores multiple augmenting paths in one go, pushing flow until no more level-respecting paths exist.
After finding a blocking flow, rebuild the level graph and repeat until the sink becomes unreachable.
Complexity Achievement
Each phase increases the shortest path length in the residual graph. Since paths can only grow from 0 to at most V-1, there are at most V phases. Each phase runs BFS (O(E)) and DFS (O(VE)), giving O(V²E) total complexity—much better than basic Ford-Fulkerson.
Key Takeaway: Dinic's algorithm achieves O(V²E) by structuring the search with BFS-built level graphs and DFS-found blocking flows, making it highly efficient for general flow networks.