Edmonds-Karp and Dinic

Ford-Fulkerson’s time depends on the size of the capacities. Two small rules make it depend only on the size of the network: always use a shortest augmenting path (Edmonds and Karp, 1972), and send along all shortest paths of one length in one go (Dinic, 1970).

Edmonds-Karp: shortest paths first

Edmonds-Karp is Ford-Fulkerson with one rule: each augmenting path is a shortest path from s to t in the residual graph, counting arcs, found by breadth-first search (GRPH-2). Step through the first variant of the figure. The tags show each station’s distance from s in the residual graph; watch them across rounds.

from collections import deque

def shortest_path(n, to, cap, adj, s, t):   # arcs in pairs, lesson 2
    via = [-1] * n                       # the arc that reached each vertex
    via[s] = -2
    q = deque([s])
    while q and via[t] == -1:
        u = q.popleft()
        for e in adj[u]:
            if cap[e] > 0 and via[to[e]] == -1:
                via[to[e]] = e
                q.append(to[e])
    return via if via[t] != -1 else None     # None: no augmenting path

The rest of each round is lesson 2’s augmenting step. Walk back from t along via (the arc into v is via[v], and its start is to[via[v] ^ 1]) and find the smallest room on the path, the bottleneck. Walk back again and push that amount: take it off each arc e and add it to its partner e ^ 1. Repeat until shortest_path returns None; the total pushed is the most flow. Writing that loop is FLOW-P2.

Why O(V · E²)

Let d(v) be the distance from s to v in the residual graph: the fewest arcs on a path. The proof has two steps.

On a shortest path every arc goes from distance k to distance k + 1. Augmenting can remove arcs (the full ones) and add new ones, and every new arc is the reverse of an arc on the path, so it goes from distance k + 1 back to k: one step closer to s, never a way that skips ahead. Removing arcs cannot shorten paths, and arcs that go one step closer to s cannot shorten a path to anything either. So distances can stay the same or grow, never shrink.

When arc u → v is a bottleneck, it fills and disappears; at that moment d(v) = d(u) + 1. For u → v to come back, some later shortest path must use the reverse arc v → u, so then d(u) = d(v) + 1. Distances never shrink (step 1), so d(u) has grown by at least 2 between the two times u → v was a bottleneck. A distance is at most V − 1 (or the vertex cannot be reached at all), so this happens at most about V / 2 times for each arc.

Every round has a bottleneck arc, and there are 2E arcs, so there are at most about V · E rounds. Each round is one BFS, O(E). So Edmonds-Karp takes O(V · E²) time (V times E times E), whatever the capacities. In the figure the distance to t goes 3, 3, 3, 4, and then t cannot be reached at all.

In practice Edmonds-Karp is far faster than this bound on most networks. But each round still runs a whole BFS to find one path. When thousands of paths have the same length, that work is repeated thousands of times.

Dinic: levels and blocking flows

Dinic’s method finds all the shortest paths of one length in one phase:

1. Run one BFS from s in the residual graph. Each vertex gets its level, its distance d(v). If t gets no level, stop.
2. Keep only arcs from a level to the next (d(v) = d(u) + 1): the level graph. Every path from s to t in it is a shortest path.
3. Send flow along paths of the level graph until no path from s to t is left in it. Such a flow is called a blocking flow. Then start the next phase.

Step 3 must not search from scratch for each path. Each vertex keeps a pointer ptr[u] to the next arc of its list to try, and the pointer only moves forward during a phase. An arc is passed over when it is full or leads to a dead end, a vertex from which t cannot be reached in the level graph. A dead end is never entered again in that phase. Step through the second variant of the figure: phase 1 sends three paths of length 3, and phase 2 one path of length 4.

# one phase, after the BFS has set level[]
ptr = [0] * n
while True:
    path, u = [], s                     # arcs from s to u
    while u != t:
        while ptr[u] < len(adj[u]):     # next usable arc of u
            e = adj[u][ptr[u]]
            if cap[e] > 0 and level[to[e]] == level[u] + 1:
                break
            ptr[u] += 1
        if ptr[u] == len(adj[u]):       # u is a dead end
            if u == s:
                break
            level[u] = -1               # never enter it again
            e = path.pop(); u = to[e ^ 1]; ptr[u] += 1
            continue
        path.append(adj[u][ptr[u]]); u = to[path[-1]]
    if u != t:
        break                           # a blocking flow
    push = min(cap[e] for e in path)
    for e in path:
        cap[e] -= push; cap[e ^ 1] += push

What Dinic costs

After a blocking flow, every shortest path of the old length has a full arc. Arcs added by the phase go one level back, so, as in step 1 above, they create no new paths of the old length or shorter. So the next phase’s distance to t is at least one more.

Inside a phase, each path found costs at most V steps to walk and fills at least one arc, which then leaves the level graph: at most E paths, O(V · E). Each step back from a dead end moves a pointer forward for good: at most E such steps. So a phase is O(V · E) and the whole method O(V² · E), that is V times V times E. On networks where every capacity is 1, a sharper count gives O(E · √V) for the bipartite networks of lesson 5 (√V is the square root of V); lesson 5’s Hopcroft-Karp method is exactly this.

Which method when

• Small total flow (F small): plain Ford-Fulkerson with any search, O(E · F), is the simplest.
• General networks: Edmonds-Karp is short and safe. On the random networks of FLOW-P3 it finishes in a fraction of a second, where depth-first Ford-Fulkerson runs for hours.
• Long, layered networks where many shortest paths share a length: Dinic. FLOW-P3’s last test has 160 layers; Edmonds-Karp needs about 13 seconds there in CPython, Dinic about half a second.
• Other methods: capacity scaling (only take paths with a bottleneck of at least Δ, halving Δ each time, O(E² · log C), E times E times log C, where C is the largest capacity), and push-relabel, which moves extra flow along one edge at a time instead of whole paths and is the fastest in many real uses. In 2022 a method that is almost linear in E was found; it is far too complex for everyday use.

Now try FLOW-P3, A full plan, fast.