|
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]] in <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<ref>{{refcite journal |Din70 last = E. A. Dinic | title = Algorithm for solution of a problem of maximum flow in a network with power estimation | journal = Soviet Math. Doklady | volume = Vol 11 | issue = | pages = 1277-1280 | publisher = Doklady | date = 1970 | url = | doi = | id = | accessdate = }}</ref>, and independently by [[Jack Edmonds]] and [[Richard Karp]] in 1972<ref>{{refcite journal |EK72 author = [[Jack Edmonds]] and [[Richard Karp|Richard M. Karp]] | title = Theoretical improvements in algorithmic efficiency for network flow problems | journal = Journal of the [[Association for Computing Machinery|ACM]] | volume = 19 | issue = 2 | pages = 248-264 | publisher = | date = 1972 | url = http://www.akira.ruc.dk/~keld/teaching/algoritmedesign_f03/Artikler/08/Edmonds72.pdf | doi = | id = | accessdate = }}</ref> (discovered earlier). Dinic's algorithm includes additional techniques that reduce the running time to <math>O(V^2 E)</math>.
==Algorithm==
The algorithm is identical to the [[Ford-Fulkerson algorithm]], except that the search order when finding the augmenting path is defined. The path found must be the shortest path which has available capacity. This can be found by a [[breadth-first search]], as we let edges have unit length. The running time of <math>O(V^2 E)</math> is found by showing that the length of the augmenting path found never decreases, that for every time one of the <math>E</math> edge becomes saturated the augmenting path must be longer than last time it was saturated, that a path is at most <math>V</math> long, and can be found in <math>O(E)</math> time. There is an accessible proof in <ref>{{refcite book |CLRS01 author = [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]] and [[Clifford Stein]] | title = [[Introduction to Algorithms]] | publisher = MIT Press and McGraw-Hill | year = 2001 | id = ISBN 0262531968 | edition = second edition | chapter = 26.2 | pages = 660-663 }}</ref>.
==Sample implementation==
==References==
<references />
* {{Note|Din70}}{{cite journal
| last = E. A. Dinic
| title = Algorithm for solution of a problem of maximum flow in a network with power estimation
| journal = Soviet Math. Doklady
| volume = Vol 11
| issue =
| pages = 1277-1280
| publisher = Doklady
| date = 1970
| url =
| doi =
| id =
| accessdate = }}
* {{Note|EK72}}{{cite journal
| author = [[Jack Edmonds]] and [[Richard Karp|Richard M. Karp]]
| title = Theoretical improvements in algorithmic efficiency for network flow problems
| journal = Journal of the [[Association for Computing Machinery|ACM]]
| volume = 19
| issue = 2
| pages = 248-264
| publisher =
| date = 1972
| url = http://www.akira.ruc.dk/~keld/teaching/algoritmedesign_f03/Artikler/08/Edmonds72.pdf
| doi =
| id =
| accessdate = }}
* {{Note|CLRS01}}{{cite book
| author = [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]] and [[Clifford Stein]]
| title = [[Introduction to Algorithms]]
| publisher = MIT Press and McGraw-Hill
| year = 2001
| id = ISBN 0262531968
| edition = second edition
| chapter = 26.2
| pages = 660-663
}}
[[Category:Network flow]]
| 