Main Page | See live article | Alphabetical index

Edmonds-Karp algorithm

In computer science, in the field of graph theory, the Edmonds-Karp algorithm is an implementation of the Ford-Fulkerson algorithm. The important additional feature is that the shortest augmenting path is used at each step, which guarantees that the computation will terminate. In most implementations, the shortest augmenting path is found using breadth-first search.

The Edmonds-Karp algorithm runs in O(VE2) time, where V and E is the number of vertices and edges in a graph, respectively.