Edmonds–Karp algorithm: Difference between revisions

Revision as of 18:00, 27 March 2006

Revision as of 06:17, 11 April 2006

Line 1:

In [[computer science]] and [[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 distinguishing 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]], which gives a running time of <math>O(VE^2)</math>. It is asymptotically slower than the [[relabel-to-front algorithm]], which runs in <math>O(V^3)</math>, but it is often faster in practice for [[sparse graph]]s. The algorithm was first published by a Russian scientist, Dinic, in 1970, and later, independently, by [[Jack Edmonds]] and [[Richard Karp]] who published it in 1972. Dinic' algorithm includes additional techniques that reduce the running time to <math>O(V^2E)</math>.

==Algorithm==