Maximum Edge-Disjoint Paths

Maximum Edge-Disjoint Paths asks how many independent routes exist between two points. It is the classic interview moment where a graph question turns out to be a max-flow question in disguise — and once you see the reduction, it is almost no code.

The slow way first

You could try to enumerate paths and greedily pick ones that do not collide. But greedy picking is a trap: an early path can "block" a better pair, and backtracking over all path combinations explodes exponentially. We need a principled way to pack paths so they never overcommit an edge.

The question to ask: what limits how many disjoint paths can coexist? Each edge can belong to at most one path. That is exactly a capacity constraint — and capacities are the language of network flow.

The idea: capacity-1 edges, then max flow

Build a flow network on the same graph. Give every edge capacity 1. Now run any max-flow algorithm from S to T. Because each edge carries at most one unit, every unit of flow traces out a path that reuses no edge, and different units cannot overlap on an edge. So:

max flow value = maximum number of edge-disjoint S→T paths.

Max flow itself works by repeatedly finding an augmenting path — any S→T path that still has spare capacity — and pushing one unit along it. With unit capacities, each push saturates one fresh path and increments the count by one.

Walk through it

Step through the animation. First the graph appears and every edge is stamped with capacity 1. Then we find the augmenting path S→A→C→T and push a unit; those edges saturate and paths ticks to 1. We search again, avoid the saturated edges, and find the disjoint path S→B→D→T; paths becomes 2. A final search finds no path with spare capacity left, so the answer is 2.

Pseudocode

give every edge capacity 1
flow = 0
while there is an augmenting path P from S to T (spare capacity on each edge):
    push 1 unit of flow along P        # subtract 1 from each edge on P
    flow = flow + 1                    # one more edge-disjoint path
return flow                            # = maximum edge-disjoint paths

The Python solution

def max_edge_disjoint_paths(graph, s, t):
    # graph[u] = list of vertices u points to
    cap = {}                       # cap[(u, v)] = 1 for every edge
    for u in graph:
        for v in graph[u]:
            cap[(u, v)] = 1
    flow = 0
    while augment(cap, s, t):      # find an S->T path with spare capacity
        # subtract 1 along that path inside augment()
        flow += 1                  # one more edge-disjoint path
    return flow

• cap[(u, v)] = 1 gives every directed edge a single unit of capacity — the whole reduction lives in this line.
• augment(cap, s, t) searches (DFS or BFS) for an S→T path whose every edge still has capacity, and subtracts 1 along it; it returns whether such a path was found.
• Each successful augment saturates one more edge-disjoint route, so we add 1 to flow.
• When no augmenting path remains, flow is the max flow, which equals the maximum number of edge-disjoint paths.

Complexity

With unit capacities the flow value F is at most the out-degree of S, so the loop runs few times. Using BFS to find augmenting paths (Edmonds-Karp) gives a clean polynomial bound.

When this pattern shows up

Practice