← Back to the graphs page
Flow Network
A digraph where edges have capacities and material "flows" from a source to a sink. Max-flow equals min-cut — the deepest duality in graph theory.
What to know
- Residual graph tracks remaining capacity plus reverse "undo" edges.
- Ford-Fulkerson repeatedly finds augmenting paths until none remain.
- Many matching and scheduling problems reduce to max-flow.
In the wild: Traffic/pipeline capacity planning, image segmentation, sports elimination, project selection.
Algorithms to reach for
Edmonds-Karp (BFS Ford-Fulkerson)
O(V · E²)Max flow with guaranteed termination
Dinic’s algorithm
O(V² · E)Max flow on larger networks via level graphs