To undo and reroute earlier flow. Residual reverse capacity preserves the ability to revise earlier routing choices.

Flow is movable material. A chosen route is not permanent: its reverse residual edges are receipts that let future augmentations refund and redirect earlier units.

What the function promises: Return maximum integer flow in a directed graph. Vertices are 0..n−1; capacities are nonnegative integers. Source and sink must differ.

from collections import deque

def maximum_flow(n, edges, source, sink):
    if source == sink: raise ValueError("Source and sink must differ")
    graph = [[] for _ in range(n)]
    def add(u, v, capacity):
        graph[u].append([v, capacity, len(graph[v])])
        graph[v].append([u, 0, len(graph[u])-1])
    for u, v, capacity in edges:
        if capacity < 0: raise ValueError("Negative capacity")
        add(u, v, capacity)
    total = 0
    while True:
        level = [-1] * n
        level[source] = 0
        queue = deque([source])
        while queue:
            u = queue.popleft()
            for v, capacity, _ in graph[u]:
                if capacity and level[v] < 0:
                    level[v] = level[u] + 1
                    queue.append(v)
        if level[sink] < 0:
            return total
        next_edge = [0] * n
        def send(u, amount):
            if u == sink: return amount
            while next_edge[u] < len(graph[u]):
                edge = graph[u][next_edge[u]]
                v, capacity, reverse = edge
                if capacity and level[v] == level[u] + 1:
                    pushed = send(v, min(amount, capacity))
                    if pushed:
                        edge[1] -= pushed
                        graph[v][reverse][1] += pushed
                        return pushed
                next_edge[u] += 1
            return 0
        while True:
            pushed = send(source, 10**30)
            if not pushed: break
            total += pushed

assert maximum_flow(4, [(0,1,3),(0,2,2),(1,2,1),(1,3,2),(2,3,3)], 0, 3) == 5

Work and storage: Dinic runs in O(V²E) generally, often faster on structured networks; storage is O(V+E).

When to recognize it: Residual reverse capacity preserves the ability to revise earlier routing choices.

Check before applying it: This is not ordinary shortest path; capacities, parallel edges, and source/sink validation matter.

Termination and numeric precision need care; integer-capacity guarantees no longer apply directly.