Edmonds-Karp
- Algorithms course
- Expert
- Lesson 27/41
- 4 min
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.
Practice 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')).
Starter code
def edmonds_karp(capacity, source, sink):
# BFS-based maximum flowSample 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'))Expected output
5
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Edmonds-Karp concepts
| Term | Meaning |
|---|---|
BFS |
Shortest path |
O(V·E²) |
Complexity |
queue |
deque |
deterministic |
Path choice |
2 What is the complexity of Edmonds-Karp?
from collections import deque- O(2ⁿ)
- O(V²)
- O(E³)
- O(V·E²) Correct answer
Explanation: Edmonds-Karp runs in O(V·E²).
3 BFS queue
queue = deque([____])queue = deque([source])Explanation: BFS starts at the source.