Content deleted Content added
edit & paper reference |
No edit summary |
||
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]].
The Edmonds-Karp algorithm [[Big O notation|runs in O(VE<sup>2</sup>) time]], where V is the number of vertices and E is the number of edges in the network.
An [http://www.cs.bgu.ac.il/~dinitz/D70.pdf algorithm] of [http://www.cs.bgu.ac.il/~dinitz/ Yefim Dinic] for the same problem was published in 1970 and has better complexity: O(V<sup>4</sup>). "An algorithm for the solution of the max-flow problem with the polynomial estimation." Dokl. Akad. Nauk SSSR 194 (1970), no.4 (in Russian); English transl.: Soviet Math. Dokl. 11 (1970), 1277-1280.
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]]''.
| |||