Flow network

On this page

Interactive

Augmenting paths, residual edges, and the minimum cut

AugmentAutoReset

Flow network (flow / capacity)

Augmenting pathMinimum cutFlow

Press Augment to find the first augmenting path.

max flow = min cut

A network carries a constrained quantity

A flow network is a finite directed graph with distinct source $s$ and sink $t$. Each original edge $e$ has finite, nonnegative capacity $c_e$. A feasible flow assigns an amount $f_e$ to every edge, obeying

$$0\le f_e\le c_e,$$

and conserving flow at every vertex except $s$ and $t$: total inflow equals total outflow. The flow value $|f|$ is the net amount leaving $s$ (equivalently, the net amount entering $t$).

Edges remain distinct even when they share endpoints. This matters for parallel edges and for reverse residual arcs: a reverse residual arc belonging to one original edge is not the same object as an original edge in the opposite direction.

Residual arcs: add flow or cancel it

For an original edge $e=(u,v)$ carrying $f_e$, its forward residual arc $u\to v$ has capacity $c_e-f_e$; it shows how much more can be sent on $e$. Its reverse residual arc $v\to u$ has capacity $f_e$; it shows how much existing flow can be canceled. Only positive-capacity residual arcs can be used.

An augmenting path is an $s$-to-$t$ path in this residual network. Let $\Delta$ be its smallest residual capacity. Along a forward arc, increase the corresponding original flow by $\Delta$; along a reverse arc, decrease it by $\Delta$. The bottleneck choice preserves every capacity bound. At each internal path vertex, the change in inflow equals the change in outflow, so conservation also remains valid. The flow value rises by $\Delta$.

Cancellation is essential, not a bookkeeping trick. Consider unit-capacity edges $s\to a$, $a\to b$, $b\to t$, $s\to b$, and $a\to t$. First send one unit along $s\to a\to b\to t$. A second augmenting path is $s\to b$, the reverse residual arc of $a\to b$ (from $b$ to $a$), then $a\to t$. This cancels the earlier $a\to b$ flow and reroutes it, producing a feasible flow of value 2.

Cuts certify an upper bound

An $s$–$t$ cut partitions the vertices into $S$ and $T$, with $s\in S$ and $t\in T$. Its capacity is the sum of capacities of original edges from $S$ to $T$:

$$c(S,T)=\sum_{e=(u,v):u\in S,v\in T}c_e.$$

Summing net outflow over $S$ cancels internal edges and gives

$$|f|=\sum_{S\to T}f_e-\sum_{T\to S}f_e\le c(S,T).$$

Thus every feasible flow is bounded by every cut. In the unit-capacity example, $S=\{s\}$ has cut capacity 2; the rerouted flow of value 2 meets this bound, certifying optimality. More generally, when no augmenting path remains, the vertices residual-reachable from $s$ define a cut whose outward original edges are saturated and inward original edges carry zero flow. Its capacity equals the current flow value, so the flow is maximum.

When augmentations terminate

The absence of an augmenting path characterizes maximum flow, but arbitrary path selection need not reach that state after finitely many steps for every capacity type. Starting from zero with integer capacities, Ford–Fulkerson keeps all flows integral; every augmentation increases the integer flow value by at least one, and that value is bounded by the finite total capacity leaving $s$. It therefore terminates. Rational capacities can be scaled to integers and have the same guarantee. With arbitrary real capacities, some path choices can produce infinitely many augmentations without reaching a maximum in finite time.

Takeaway: residual forward arcs add flow, reverse arcs allow rerouting, and cuts provide a certificate that no larger flow is possible.