Edmonds–Karp algorithm: Difference between revisions

Revision as of 22:14, 29 January 2005

Revision as of 03:29, 30 March 2005

Line 1:

In [[computer science]], in the field ofand [[graph theory]], the '''Edmonds-Karp algorithm''' is an implementation of the ''[[Ford-Fulkerson algorithm|Ford-Fulkerson method]]'', for computing the [[maximum flow problem|maximum flow]] in a [[flow network]]. The important additionaldistinguishing 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 a [[breadth-first search]].

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

The Edmonds-Karp algorithm was elucidated in the 1972 paper "Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems," by [[Jack Edmonds]] and [[Richard Karp]], in the ''Journal of the [[Association for Computing Machinery|ACM]]''.

==External link==

[http://delivery.acm.org/10.1145/330000/321699/p248-edmonds.pdf The 1972 paper in PDF format, at the ''JACM'' Web site]

{{compu-stub}}