Visualize & Master
Algorithms & Data Structures
Explore classic & modern sorting algorithms, efficient searching techniques, and interactive data structure visualizations — all with real-time step-by-step animation, comparisons, swaps, and Big-O metrics.
About Maximum flow finds the largest amount of flow a network can route from a source node to a sink node without exceeding any edge capacity
Maximum flow finds the largest amount of flow a network can route from a source node to a sink node without exceeding any edge capacity.
The Edmonds-Karp algorithm repeatedly BFS-es for the shortest augmenting path in the residual graph and pushes flow along it, terminating when no path remains — by the max-flow/min-cut theorem, the result equals the capacity of the minimum cut.
How It Works
Each edge carries a flow f ≤ capacity c.
The residual graph tracks how much more can be sent forward (c − f) and how much can be "undone" backward (f).
Edmonds-Karp runs BFS from the source to find the shortest path to the sink using edges with positive residual capacity; the bottleneck is the smallest residual capacity along the path, which is added to forward edges and subtracted from reverse edges.
Each augmentation strictly increases flow, and BFS guarantees at most O(V·E²) time overall.
Time & Space Complexities
| Operation | Time | Space |
|---|---|---|
| Edmonds-Karp (BFS augmenting paths) | O(V·E²) | O(V + E) |
| Max-flow / min-cut theorem | max flow = min cut capacity | — |
| Augmentation step | O(E) | O(V) BFS |
| Residual graph | forward c−f, backward f | O(E) |
Best Use Cases
- Network capacity planning and data routing
- Bipartite matching (reduce to max flow with a super-source and super-sink)
- Project scheduling and task assignment problems
- Image segmentation (graph cut optimization)
- Maximum bipartite matching in matchmaking and pairing systems
Worked Example
Max flow from S to T via Edmonds-Karp
Input: S→A(10), S→B(8), A→B(2), A→C(5), B→D(8), C→T(7), C→D(7), D→T(10)- 1 BFS finds the shortest augmenting path S → A → C → T with residual capacity min(10, 5, 7) = 5.
- 2 Push 5 units along it: S–A drops to 5, A–C to 0, C–T to 2; reverse edges record the ability to undo.
- 3 BFS finds S → B → D → T with bottleneck min(8, 8, 10) = 8.
- 4 Push 8 units: S–B to 0, B–D to 0, D–T to 2.
- 5 No more path from S to T exists in the residual graph, so the algorithm terminates.
- 6 Total flow = 5 + 8 = 13, which equals the capacity of the minimum cut by the max-flow/min-cut theorem.
Pseudocode
maxFlow = 0
while BFS finds path from source to sink
in the residual graph:
bottleneck = min residual capacity
along the path
for each edge on the path:
forward edges: flow += bottleneck
reverse edges: flow -= bottleneck
maxFlow += bottleneck
return maxFlow Edmonds-Karp Algorithm
BFS finds the shortest augmenting path; flow is pushed until the residual graph has none left.