Algorithms
Edmonds-Karp
BFS-based Edmonds-Karp algorithm.
Edmonds-Karp
Edmonds-Karp is Ford-Fulkerson with BFS. The augmenting path is always chosen to be the shortest (fewest edges) one.
Using BFS guarantees a polynomial complexity of O(V·E²). Unlike Ford-Fulkerson, path selection is deterministic.
This robustness makes Edmonds-Karp a preferred method in practice.
BFS path search
Edmonds-Karp uses BFS to find augmenting paths. Starting from the source, we record each node's parent; when we reach the sink, the parent chain gives the path.
During BFS we only follow edges with positive residual capacity. This ensures a valid path in the residual graph.
The bottleneck on the found path is the minimum edge capacity; flow increases by that amount.
Exercise edmonds_karp function
Write edmonds_karp(capacity, source, sink). Return the maximum flow using BFS. Print 5 with print(edmonds_karp([('s','a',3), ('s','b',2), ('a','t',2), ('b','t',3), ('a','b',1)], 's', 't')).
Show example solution
def edmonds_karp(capacity, source, sink):
# BFS-based maximum flow
from collections import deque, defaultdict
graph = defaultdict(dict)
for u, v, c in capacity:
graph[u][v] = graph[u].get(v, 0) + c
graph[v][u] = graph[v].get(u, 0)
max_flow = 0
while True:
parent = {source: None}
queue = deque([source])
while queue:
u = queue.popleft()
for v in graph[u]:
if v not in parent and graph[u][v] > 0:
parent[v] = u
queue.append(v)
if sink not in parent:
break
flow = float('inf')
v = sink
while v != source:
u = parent[v]
flow = min(flow, graph[u][v])
v = u
v = sink
while v != source:
u = parent[v]
graph[u][v] -= flow
graph[v][u] = graph[v].get(u, 0) + flow
v = u
max_flow += flow
return max_flow
print(edmonds_karp([('s','a',3), ('s','b',2), ('a','t',2), ('b','t',3), ('a','b',1)], 's', 't'))
Test yourself
-
Edmonds-Karp concepts
- BFS
- Shortest path
- O(V·E²)
- Complexity
- queue
- deque
- deterministic
- Path choice
-
What is the complexity of Edmonds-Karp?
from collections import deque
Show answer
O(V·E²) — Edmonds-Karp runs in O(V·E²).
-
BFS queue
queue = deque([____])
Show answer
queue = deque([source])
Next lesson: Max-flow min-cut
