Introduction
Network flow models a directed graph where each edge has a capacity representing the maximum amount of 'flow' it can carry, and asks how much total flow can be pushed from a source vertex to a sink vertex without violating any capacity constraint. This abstraction captures a surprisingly wide range of problems: bandwidth allocation in computer networks, bipartite matching (assigning workers to jobs), scheduling, and image segmentation. The central result, the max-flow min-cut theorem, states that the maximum amount of flow achievable equals the minimum total capacity of edges that, if removed, would disconnect the source from the sink -- a 'min cut'.
Cricket analogy: Network flow is like modeling how many runs can be pushed through a chain of running partners between striker and boundary, where each partner's capacity, running speed, limits the total, and the min cut is the slowest link in the chain.
Algorithm/Syntax
from collections import deque, defaultdict
def edmonds_karp(capacity, source, sink, n):
"""capacity: dict[(u, v)] = cap, defined for both directions (0 if no edge).
n: number of vertices. Returns the max flow value.
"""
graph = defaultdict(list)
cap = defaultdict(int)
for (u, v), c in capacity.items():
graph[u].append(v)
graph[v].append(u) # reverse edge enables 'undoing' flow
cap[(u, v)] += c
def bfs_find_path():
parent = {source: None}
queue = deque([source])
while queue:
u = queue.popleft()
if u == sink:
break
for v in graph[u]:
if v not in parent and cap[(u, v)] > 0:
parent[v] = u
queue.append(v)
if sink not in parent:
return None
path = []
v = sink
while parent[v] is not None:
path.append((parent[v], v))
v = parent[v]
return list(reversed(path))
max_flow = 0
while True:
path = bfs_find_path()
if path is None:
break
bottleneck = min(cap[(u, v)] for u, v in path)
for u, v in path:
cap[(u, v)] -= bottleneck # use forward capacity
cap[(v, u)] += bottleneck # increase residual reverse capacity
max_flow += bottleneck
return max_flowExplanation
Ford-Fulkerson is the general method: repeatedly find an augmenting path from source to sink through edges with remaining (residual) capacity, push as much flow as the path's bottleneck edge allows, and update the residual graph by decreasing forward capacity and increasing reverse capacity (so flow can later be 'rerouted' or partially undone if it turns out suboptimal). This continues until no augmenting path exists, at which point the flow is maximum. Edmonds-Karp is a specific implementation of Ford-Fulkerson that always chooses the shortest augmenting path (by number of edges, found via BFS) rather than an arbitrary one; this choice guarantees the algorithm terminates in a polynomial number of iterations even with irrational or unusual capacities, whereas a naive Ford-Fulkerson using DFS or arbitrary path selection can be slow or fail to terminate in pathological cases with irrational capacities.
Cricket analogy: Ford-Fulkerson is like repeatedly finding the best available running route between wickets and pushing as many runs as the slowest fielder allows, updating who's now tired, the residual capacity; Edmonds-Karp always picks the shortest route first via BFS, guaranteeing the run chase finishes in reasonable time.
Example
# Vertices 0=source, 3=sink; edges with capacities
capacity = {
(0, 1): 3, (0, 2): 2,
(1, 2): 1, (1, 3): 2,
(2, 3): 3,
}
print(edmonds_karp(capacity, source=0, sink=3, n=4)) # 4
# Trace: augmenting path 0->1->3 pushes min(3, 2) = 2 units (edge (1,3) saturates).
# Next augmenting path 0->2->3 pushes min(2, 3) = 2 units (edge (0,2) saturates).
# Next BFS search finds no more augmenting paths (0->1->2->3 is blocked because
# (1,3) and (0,2) are saturated), so the algorithm stops with total max flow = 4.
# This matches the min cut {(0,1), (2,3)-portion} whose combined effective
# capacity across the source side of the cut sums to 4.Complexity
Edmonds-Karp runs in O(V * E^2) time: each BFS augmenting-path search costs O(E), and it can be shown that at most O(V * E) augmenting paths are needed before the algorithm terminates. This is a strict improvement over generic Ford-Fulkerson, whose runtime O(E * max_flow) depends on the numeric value of the maximum flow and can be exponential for poorly chosen augmenting paths on graphs with large integer capacities. More advanced algorithms like Dinic's algorithm achieve O(V^2 * E), better still for large graphs.
Cricket analogy: Always choosing the shortest available running route, Edmonds-Karp, bounds the number of run-chasing attempts polynomially, unlike blindly choosing any route, generic Ford-Fulkerson, which could take forever on a huge target; a more advanced fielding strategy, Dinic's, does even better on a big chase.
Key Takeaways
- Max-flow min-cut theorem: the maximum flow from source to sink equals the minimum total capacity of a cut separating them.
- Ford-Fulkerson repeatedly finds augmenting paths in the residual graph and pushes flow until none remain.
- Edmonds-Karp specializes Ford-Fulkerson by using BFS to always pick the shortest augmenting path, guaranteeing O(V * E^2) time.
- Residual (reverse) edges let the algorithm 'undo' previously assigned flow if a better routing is later found.
- Network flow underlies bipartite matching, scheduling, and segmentation problems, not just literal transportation networks.
Practice what you learned
1. What does the max-flow min-cut theorem state?
2. What distinguishes Edmonds-Karp from generic Ford-Fulkerson?
3. Why does the algorithm add a reverse (residual) edge each time it pushes flow along a forward edge?
4. What is the time complexity of the Edmonds-Karp algorithm on a graph with V vertices and E edges?
Was this page helpful?
You May Also Like
Bellman-Ford Algorithm
A single-source shortest path algorithm that handles negative edge weights and detects negative-weight cycles.
Union-Find and Disjoint Sets
A near-constant-time data structure for tracking disjoint sets, essential for cycle detection and Kruskal's MST.
The Greedy Algorithm Paradigm
Learn how greedy algorithms build solutions one locally optimal choice at a time, and when that strategy actually yields a global optimum.