Edmonds–Karp algorithm: Difference between revisions

Revision as of 19:52, 8 August 2003

Revision as of 15:27, 6 October 2003

Line 1:

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

The Edmonds-Karp algorithm [[Big O notation|runs]] in O(VE²) time, where V and E is the number of vertices and edges in a [[graph]], respectively.