Revision as of 10:29, 20 July 2004 edit Sesse (talk \| contribs) 177 edits m Fixed termination condition (F-F always terminates, but might do so very slowly with large weights) ← Previous edit		Revision as of 10:31, 20 July 2004 edit undo Sesse (talk \| contribs) 177 edits m Revert previous change :-) Next edit →
Line 1: 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 polynomial time~~. In most implementations, the shortest augmenting path is found using [[breadth-first search]]. The Edmonds-Karp algorithm [[Big O notation\|runs]] in O(VE<sup>2</sup>) time, where V and E is the number of vertices and edges in a [[graph theory\|graph]], respectively.

Edmonds–Karp algorithm: Difference between revisions