1. Networks and flows

A flow network is a finite directed graph $G=(V,E)$ with two distinct vertices: a source s and a sink t. Every edge has a finite, nonnegative capacity c(u,v). Its flow f(u,v) is the amount actually sent along that edge.

Set f(u,v) = 0 for missing edges. We use nonnegative flow on each original edge; we do not impose f(u,v) = −f(v,u). The flow value is the net outflow from the source, equal to the net inflow into the sink:

The maximum-flow problem asks for a feasible flow maximizing |f|. Do not add flows over all edges: the same amount may traverse several edges. If no flow leaves t or enters s, simply sum the inflow into t or the outflow from s.

2. The residual network: add and reconsider

For each original edge u → v, create two possibilities in the residual network G_f. Keep only those with strictly positive residual capacity.

• Forward, u → v: capacity c(u,v) − f(u,v). This much extra flow can be added.
• Backward, v → u: capacity f(u,v). This much previously assigned flow can be cancelled.

Example: an edge of capacity 7 carrying 4 leaves 3 units forward and 4 backward. A reverse edge is not a new pipe: using it reduces flow on the original edge, freeing resources for another route.

An augmenting path is a path from s to t in the residual network. Its bottleneck Δ is the smallest residual capacity on that path. Add Δ on forward edges and subtract Δ on backward edges. The total flow value increases by Δ.

3. One network, two ways to augment flow

Labels show flow / capacity. Ford–Fulkerson with DFS visits a and then b first, making a choice that will be revised using the reverse edge b → a. Edmonds–Karp uses BFS to choose paths with the fewest residual edges.

4. A cut certifies the maximum

An s–t cut partitions V into (S,T), with s ∈ S and t ∈ T. Its capacity c(S,T) is the sum of original capacities from S to T; edges from T to S do not count.

By conservation, the net flow across any cut equals |f|. Forward flow cannot exceed the cut capacity and return flow is nonnegative, so |f| ≤ c(S,T). The max-flow min-cut theorem says this bound can be attained:

Why no augmenting path means optimality

1. Let S contain every vertex reachable from s in the residual network. If t is unreachable, (S,V ∖ S) is a cut.
2. Every original edge from S to T is saturated; otherwise its residual edge would reach another vertex.
3. Every original edge from T to S has zero flow; otherwise its reverse residual edge would cross from S to T.
4. Thus |f| = c(S,T). We have both a maximum flow and a minimum cut.

Equivalently, a flow is maximum if and only if its residual network has no augmenting path. Maximum flows and minimum cuts need not be unique.

5. Ford–Fulkerson and Edmonds–Karp

Ford–Fulkerson is a method: repeat augmentations while a residual path exists. Edmonds–Karp specifies how to choose it: BFS finds a shortest path by edge count, not a path of greatest capacity.

initialize f = 0 on all edges
while a path P from s to t exists in the residual network:
    Δ = minimum residual capacity on P
    for each residual edge e of P:
        residual[e] -= Δ
        residual[reverse(e)] += Δ
    value += Δ
return f and vertices reachable from s in the residual network

With residual pairs, recover each original edge’s flow as initial capacity minus forward residual capacity. Every update must also update the reverse edge.

Both use O(n + m) space with adjacency lists. The usual Edmonds–Karp bound considers vertices in the relevant network; initializing isolated vertices adds O(n). BFS distances in the residual network never decrease: an edge can become a bottleneck only O(n) times, giving O(nm) augmentations.

With rational capacities Ford–Fulkerson terminates, but scaling to integers can produce very large numbers. With irrational capacities and arbitrary path choices it may not terminate. Integer capacities guarantee that an integral maximum flow exists, since each augmentation preserves integrality; this does not mean every optimal solution must be integral.

6. Applications

• Bipartite matching: add s → L, edges L → R and R → t, all of capacity 1. An integral maximum flow selects the largest set of disjoint pairs.
• Edge-disjoint paths: with unit capacities, the maximum value counts how many s–t paths can avoid sharing edges.
• Vertex capacities: split v into v_in and v_out, connected by an edge of the desired vertex capacity; redirect incoming and outgoing edges.
• Multiple sources or sinks: add a super-source or super-sink, with capacities reflecting supply and demand. When “infinite” capacity is needed, use a sufficient finite bound, such as the sum of original capacities.

Maximum flow optimizes quantity. Optimizing a cost per unit transported requires a different problem: minimum-cost flow.

7. Common mistakes

• Searching only unsaturated original edges. This misses reverse edges and can stop before the optimum.
• Confusing saturated with final. A full edge can be partially emptied by a later reverse augmentation.
• Adding both directions across a cut. Capacity counts only S → T; net flow subtracts T → S.
• Interpreting the result as one route. Flow can split across multiple paths and a feasible solution may contain cycles.

8. Try before opening the solution