The Edmonds-Karp algorithm reference article from the English Wikipedia on 24-Jul-2004 (provided by Fixed Reference: snapshots of Wikipedia from wikipedia.org)

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(VE²) time, where V and E is the number of vertices and edges in a graph, respectively.

This is the "Edmonds-Karp algorithm" reference article from the English Wikipedia. All text is available under the terms of the GNU Free Documentation License. See also our Disclaimer.