Graph Theory37 sections · 1633 units
Open in Course

Edmonds-Karp Algorithm

BFS for shortest augmenting...

Edmonds-Karp is a specific implementation of Ford-Fulkerson.

Instead of finding any augmenting path, it uses BFS to find the shortest augmenting path (fewest edges). Why BFS?

It guarantees termination in O(VE2)O(VE^2) time. If you pick paths arbitrarily, the algorithm might not terminate (if capacities are irrational). BFS also makes implementation direct. You already know how to write BFS. Run it on the residual graph and track the path from source to sink.

Space complexity is O(V+E)O(V + E) for the data structures used.