Edmonds–Karp algorithm

From PEGWiki
Jump to: navigation, search

The Edmonds–Karp algorithm is a special case of the Ford–Fulkerson method that always chooses a shortest augmenting path at each iteration. It solves the maximum flow problem in O(VE^2) time.

The algorithm[edit]

input flow network (V, s, t, c)
F ← 0
for u ∈ V
    for v ∈ V
        f[u, v] ← 0
        r[u, v] ← c[u, v]
while t is reachable from s in (V, s, t, r)
    find a shortest augmenting path (s = v[0], v[1], ..., v[n] = t) with BFS
    m ← ∞
    for i ∈ [0, n)
        m ← min(m, r[v[i], v[i+1]])
    for i ∈ [0, n)
        f[v[i], v[i+1]] ← f[v[i], v[i+1]] + m
        f[v[i+1], v[i]] ← f[v[i+1], v[i]] - m
        r[v[i], v[i+1]] ← r[v[i], v[i+1]] - m
        r[v[i+1], v[i]] ← r[v[i+1], v[i]] + m
    F ← F + m
output max flow f
output max flow value F


A trivial upper bound of O((E+V)M) can be derived in the case that all edge capacities are integers. Each iteration of the algorithm uses breadth-first search, which takes O(E+V) time, to find a shortest augmenting path, and there are at most M iterations, where M is the value of the max flow, since in each step the total flow so far increases by at least one unit.

As a matter of fact, however, the Edmonds–Karp algorithm's running time has a capacity-independent bound, O(VE^2). The proof is not trivial and can be found in a textbook such as Introduction to Algorithms by Cormen et al.