Edmonds-Karp
Ford-Fulkerson with a specific rule: always augment along the shortest path (fewest edges), found by BFS. That single choice guarantees termination in O(V·E²) regardless of capacity values — no adversarial graph can make it slow.
- Category
- Graphs
- Time complexity
- O(V · E²)
- Space complexity
- O(V + E)
Pseudocode
while BFS finds an S→T path in residual graph (BFS ⇒ shortest path by edge count) bottleneck = min residual on it push bottleneck flow along it
Reference implementation
while path := bfs(residual_graph, S, T):
b = min(residual capacities on path)
for edge in path: update_flow(edge, b)
flow += b
# BFS guarantees polynomial time