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.