Visualizer CodeViz · Algorithms, visualized

Part II · Maximum flow · week 4

Ford–Fulkerson (max-flow)

Push flow along any path with spare capacity, allowing yourself to cancel earlier flow. When no such path is left, the flow is maximum — and it exposes a minimum cut.

Run the animation, step by step → generated live from any input you type — nothing is pre-recorded

Cost and properties

with BFS paths≤ V·E/2 augmentations
each searchO(E)
provesmax-flow = min-cut
backward edgesessential

Reference: Sedgewick & Wayne, §6.4; Ford–Fulkerson 1956, Edmonds–Karp 1972.

Ford–Fulkerson (max-flow) in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

from collections import deque

class FordFulkerson:
    # Repeatedly find an augmenting path in the RESIDUAL network and push
    # the bottleneck amount along it. Choosing the path by BFS (fewest
    # edges) is Edmonds-Karp, which bounds the number of augmentations.

    def __init__(self, capacity, s, t):
        self.cap = capacity               # cap[v][w], 0 if no edge
        self.flow = [[0] * len(capacity) for _ in capacity]
        self.value = 0.0
        while True:
            path = self._augmenting_path(s, t)
            if path is None:
                break                     # no path left: flow is MAXIMUM
            bottle = min(self._residual(v, w) for v, w in path)
            for v, w in path:
                if self.cap[v][w] > 0:
                    self.flow[v][w] += bottle   # forward: add flow
                else:
                    self.flow[w][v] -= bottle   # backward: CANCEL flow
            self.value += bottle

    def _residual(self, v, w):            # spare capacity v -> w
        if self.cap[v][w] > 0:
            return self.cap[v][w] - self.flow[v][w]
        return self.flow[w][v]            # undo-able flow counts too

    def _augmenting_path(self, s, t):     # BFS in the residual network
        edge_to, q = {s: None}, deque([s])
        while q:
            v = q.popleft()
            for w in range(len(self.cap)):
                if w not in edge_to and self._residual(v, w) > 0:
                    edge_to[w] = v
                    q.append(w)
        if t not in edge_to:
            return None
        path, x = [], t
        while edge_to[x] is not None:
            path.append((edge_to[x], x))
            x = edge_to[x]
        return list(reversed(path))

Why it works

The residual network is the whole idea

For each edge you can either add flow (up to its spare capacity) or remove flow you previously sent (up to the flow currently on it). The residual network makes both look like ordinary forward edges, so finding an augmenting path is just a graph search — and the dashed curves in the picture are those undo edges appearing as flow accumulates.

Without the backward option the algorithm gets stuck in a locally-good but non-maximum flow: send flow the wrong way early and there is no way to take it back. Cancellation is what makes “any augmenting path” safe rather than a gamble.

Why it stops, and what stopping proves

When no augmenting path exists, let S be the set of vertices still reachable from the source in the residual network. Every edge from S to its complement must be saturated and every edge back into S must be empty — so the flow equals the capacity of that cut. Since no flow can ever exceed any cut, this flow is maximum and this cut is minimum. That is the max-flow min-cut theorem, and the algorithm's termination is its proof.

Choosing the path matters

Ford–Fulkerson says “any augmenting path”, and with a bad choice it can take a very long time — with irrational capacities it need not even terminate. Load the why the path choice matters preset: BFS finds the two fat routes and finishes in 2 augmentations, but a search that kept picking the path through the thin middle edge would need 2000, each one pushing a single unit and then cancelling it back.

Choosing the shortest augmenting path (Edmonds–Karp) bounds the augmentations at V·E/2 regardless of capacities. A rare and instructive case where a choice inside a loop changes the complexity class.

Reductions

Bipartite matching, baseball elimination, image segmentation, scheduling and project selection all become max-flow problems. That is the point of the last week of Part II: you stop inventing algorithms and start reducing your problem to one that is already solved.

What to try in the animation

v-w:capacity. The default is tinyFN.txt from the course; its max flow is 4. Edge labels read flow / capacity, and dashed curves are residual (undo) edges.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

Open Ford–Fulkerson (max-flow) in the player →