Edmonds-Karp
DSA · Graphs
Theory
Edmonds-Karp is Ford-Fulkerson with one rule: always choose the shortest augmenting path, found with breadth-first search. That small change guarantees a polynomial running time of O(V * E^2), no matter how large the capacities are, while plain DFS-based Ford-Fulkerson can take time proportional to the flow value itself. Each BFS finds the path with the fewest edges in the residual graph, the bottleneck capacity along it is pushed, and the residual capacities are updated in both directions. The algorithm stops when BFS can no longer reach the sink. Recording the parent of each vertex during BFS lets you walk the path back from sink to source.
Why we use it
It gives predictable performance for max-flow problems and is the version most textbooks and interviewers expect you to implement.
When to use it
Use it for max-flow and bipartite matching on small to medium graphs. For very large networks, faster algorithms such as Dinic's are used.
How it works
- flow = 0
- BFS for the shortest path s -> t in residual graph
- Path found? Yes: Bottleneck b, update residuals, flow += b. No: Stop: maximum flow.
- Repeat BFS
Syntax
while BFS finds path s -> t in residual graph:
bottleneck = min capacity on path
update residual (forward -= b, backward += b)
Time O(V * E^2)Example
from collections import deque
def edmonds_karp(cap, s, t):
n = len(cap)
residual = [row[:] for row in cap]
flow, paths = 0, []
while True:
parent = [-1] * n
parent[s] = s
q = deque([s])
while q and parent[t] == -1:
u = q.popleft()
for v in range(n):
if parent[v] == -1 and residual[u][v] > 0:
parent[v] = u
q.append(v)
if parent[t] == -1:
return flow, paths
path, v, b = [t], t, float("inf")
while v != s:
b = min(b, residual[parent[v]][v])
v = parent[v]
path.append(v)
v = t
while v != s:
residual[parent[v]][v] -= b
residual[v][parent[v]] += b
v = parent[v]
flow += b
paths.append((path[::-1], b))
cap = [
[0, 16, 13, 0, 0, 0],
[0, 0, 10, 12, 0, 0],
[0, 4, 0, 0, 14, 0],
[0, 0, 9, 0, 0, 20],
[0, 0, 0, 7, 0, 4],
[0, 0, 0, 0, 0, 0],
]
total, paths = edmonds_karp(cap, 0, 5)
for p, b in paths:
print("path", p, "pushes", b)
print("Maximum flow:", total)Key points
- Ford-Fulkerson using BFS for the shortest augmenting path
- Runs in O(V * E^2) regardless of capacities
- Parent array reconstructs each path
- Same answer as Ford-Fulkerson, more predictable speed