Wikipedia

Edmonds–Karp algorithm

This is an old revision of this page, as edited by Zero0000 (talk | contribs) at 15:32, 22 October 2005 (Remove inappropriate addition. Make a new article for Dinic's algorithm if you want.). 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 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 ACM.

The 1972 paper in PDF format, at the JACM Web site

 

This computing article is a stub. You can help Wikipedia by expanding it.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Edmonds–Karp_algorithm&oldid=26190628"