Edmonds–Karp algorithm: Difference between revisions

Revision as of 20:38, 18 August 2006

Revision as of 22:48, 30 August 2006

Line 3:

==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>{{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 02625319680-262-53196-8 | edition = second edition | chapter = 26.2 | pages = 660-663 }}</ref>.

==Sample implementation==

Line 11:

'''def''' edmonds_karp(C, source, sink):

n = len(C) ''# C is the capacity matrix''

F = [[0]] * n '''for''' i '''in''' xrange(n)]

''# residual capacity from u to v is C[u][v] - F[u][v]''

Line 98:

</table>

Notice how the length of the [[augmenting path]] found by the algorithm never decreases. The paths found are the shortest possible. The flow found is equal to the capacity across the [[max_flow_min_cut_theoremmax flow min cut theorem|smallest cut]] in the graph separating the source and the sink. There is only one minimal cut in this graph, partitioning the nodes into the sets <math>\{A,B,C,E\}</math> and <math>\{D,F,G\}</math>, with the capacity <math>c(A,D)+c(C,D)+c(E,G)=3+1+1=5</math>.

==References==