Network Flow: Max-Flow / Min-Cut

What you'll learn

A flow network asks: how much can move from a source to a sink through edges with limited capacity? The answer — max flow — solves a startling range of problems, and it equals the capacity of the cheapest way to cut the network in two.

By the end you'll be able to:

• Define a flow network and a valid flow
• Find max flow with augmenting paths and the residual graph
• State the max-flow min-cut theorem

Flow networks

A flow network is a directed graph with a source S, a sink T, and a capacity on each edge. A valid flow never exceeds any edge's capacity, and — except at S and T — flow in equals flow out at every vertex. We want to maximize the total leaving S.

Augmenting paths & the residual graph

The idea: find a path from S to T with spare capacity (an augmenting path), push as much flow as its tightest edge allows, and repeat. The trick is the residual graph: each unit of flow also creates a backward edge that lets a later path cancel it — which is what makes the method reach the true maximum.

Watch it flow

Each edge shows flow / capacity. Step through the augmenting paths as flow is pushed from S to T:

In code

from collections import deque

def max_flow(cap, s, t, n):        # cap[u][v] = residual capacity
    total = 0
    while True:
        parent = [-1] * n
        parent[s] = s
        q = deque([s])
        while q:                   # BFS for an augmenting path (Edmonds-Karp)
            u = q.popleft()
            for v in range(n):
                if parent[v] == -1 and cap[u][v] > 0:
                    parent[v] = u
                    q.append(v)
        if parent[t] == -1:
            break                  # no augmenting path -> done
        bottleneck = float("inf")  # smallest residual on the path
        v = t
        while v != s:
            bottleneck = min(bottleneck, cap[parent[v]][v]); v = parent[v]
        v = t
        while v != s:              # push flow, add backward residual
            cap[parent[v]][v] -= bottleneck
            cap[v][parent[v]] += bottleneck
            v = parent[v]
        total += bottleneck
    return total

Max-flow min-cut

A cut splits the vertices into a source side and a sink side; its capacity is the total of edges crossing from source side to sink side. The celebrated max-flow min-cut theorem says the maximum flow equals the minimum cut capacity — the flow is limited exactly by the network's tightest bottleneck. In the demo, max flow 5 matches the cut around S (capacity 3 + 2).

Recap & quick check

One of flow's most elegant applications deserves its own module: pairing things up. Next up: Module 29 — Bipartite Matching & Assignment.