Edmonds–Karp algorithm

In computer science and graph theory, the Edmonds-Karp algorithm is an implementation of the Ford-Fulkerson method for computing the maximum flow in a flow network. The distinguishing feature is that the shortest augmenting path is used at each step, which guarantees that the computation will terminate. In most implementations, the shortest augmenting path is found using a breadth-first search.

The Edmonds-Karp algorithm runs in O(VE²) time, where V is the number of vertices and E is the number of edges in the network. Hence it is asymptotically slower than the relabel-to-front algorithm, which runs in O(V³), but it is often faster in practise for sparse graphs.

The algorithm was first published by a Russian scientist, Dinic, in 1970, and later, independently, by Edmonds and Karp who published it in 1972. Dinic' algorithm includes additional techniques that reduce the running time to O(EV²).

Sample implementation

Python implementation:

def edmonds_karp(C, source, sink):
    n = len(C) # C is the capacity matrix
    F = [[0] * n for _ in xrange(n)]
    # residual capacity from u to v is C[u][v] - F[u][v]

    while True:
        path = bfs(C, F, source, sink)
        if not path:
            break
        flow = Inf # traverse path to find smallest capacity
        for i in xrange(len(path) - 1):
            u,v = path[i], path[i+1]
            flow = min(flow, C[u][v] - F[u][v])
        # traverse path to update flow
        for i in range(len(path) - 1):
            u,v = path[i], path[i+1]
            F[u][v] += flow
            F[v][u] -= flow
    return sum([F[source][i] for i in xrange(n)])

def bfs(C, F, source, sink):
    P = [-1] * len(C) # parent in search tree
    P[source] = source
    queue = [source]
    while len(queue):
        u = queue.pop(0)
        for v in xrange(len(C)):
            if C[u][v] - F[u][v] > 0 and P[v] == -1:
                P[v] = u
                queue.append(v)
                if v == sink:
                    path = []
                    while True:
                        path.insert(0, v)
                        if v == source:
                            break
                        v = P[v]
                    return path
    return None

References

• 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)