Edmonds–Karp algorithm

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

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

Complexity

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.