Wikipedia

Edmonds–Karp algorithm

This is an old revision of this page, as edited by Zero0000 (talk | contribs) at 09:31, 16 November 2005 (Dinic' algorithm is more sophisticated than E-K, that's why the running time is better.). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In computer science and graph theory, the Edmonds-Karp algorithm is an implementation of the Ford-Fulkerson method for computing the 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.

The Edmonds-Karp algorithm runs in O(VE2) time, where V is the number of vertices and E is the number of edges in the network.

The algorithm was first published by a Russian scientist, Dinic, in 1970, and later, independently, by Edmonds and Karp who published it in 1972. Dinic' algorithm includes additional techniques that reduce the running time to O(EV2).

References

  • E. A. Dinic, Algorithm for solution of a problem of maximum flow in a network with power estimation, Soviet Math. Doklady, Vol 11 (1970) pp1277-1280.
  • J. Edmonds and R. M. Karp, Theoretical improvements in algorithmic efficiency for networkl flow problems, Journal of the ACM, Vol 19, No. 2 (1972) pp248-264. PDF (needs subscription)
Retrieved from "https://en.wikipedia.org/w/index.php?title=Edmonds–Karp_algorithm&oldid=28490981"