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.
Given that the augmenting path is found with a Breadth-first Search , the running time of the Edmonds-Karp algorithm is . This can be seen from the following argument:
|
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
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
and
, with the capacity
.
- 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 network flow problems, ''Journal of the ACM '', Vol 19, No. 2 (1972) pp248-264. PDF (needs subscription)
