|
In computer science, in the field of graph theory, the Edmonds-Karp algorithm is an implementation of the Ford-Fulkerson algorithm, for computing the maximum flow in a flow network. 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 is the number of vertices and E is the number of edges in a graph.
|
