Which algorithm for the maximum flow problem improves on Ford-Fulkerson by always choosing the shortest augmenting path using BFS?
Show answer
Edmonds-Karp algorithm
The Edmonds-Karp algorithm is a specific implementation of the Ford-Fulkerson method that runs in O(VE^2) time. By using BFS to find augmenting paths, it guarantees termination even with irrational edge capacities.
Also asked as:
- Which implementation of the Ford-Fulkerson method uses Breadth-First Search to find the shortest augmenting paths?