Recipe

Build the residual graph and find an augmenting path

Use when: you have a flow network with a partial or zero flow already in place and need to know whether more flow can still reach t

Goal: an augmenting path with its bottleneck, ready to push through, or confirmation that none remains

Taught in Residual graphs and augmenting paths · a later section extends this recipe with more cases

1. 1

   For every original edge (u,v), add a forward edge with residual capacity c(u,v)-f(u,v) if that's positive, and a backward edge with residual capacity f(u,v) if that's positive.

   Example

   On s\to a\to b\to t with c(s,a)=4, c(a,b)=2, c(b,t)=5, take the flow f(s,a)=2, f(a,b)=2, f(b,t)=2. Forward s\to a gets residual 4-2=2; forward a\to b gets 2-2=0, so it's absent; backward b\to a gets residual 2 instead.

   Why: these are the only two ways a unit of flow could move next, either using unused capacity or undoing flow already sent.

2. 2

   Starting at s, follow only edges with positive residual capacity, in any order, until t is reached or every reachable vertex has been tried.

   Example

   Same flow as above, but now c(a,t)=3 and f(a,t)=0. From s, edge s\to a is open (residual 2). From a, edge a\to b is closed (residual 0), but a\to t is open (residual 3), reaching t directly.

   • a path to t exists — continue to the next step to find its bottleneck.
   • no path to t exists in the residual graph — the current flow is already maximum; stop here.
   • Not yet: proving that "no augmenting path" really does mean "maximum flow" — covered in The max-flow min-cut theorem

   ⚡ Shortcut

   On a small hand-drawn network, skip listing every edge's residual capacity up front. Compute residual capacities only for edges leaving vertices already reached, one step at a time.

   Why: any edge with zero residual capacity can't carry another unit, so the search must avoid it.

3. 3

   The bottleneck is the smallest residual capacity among all the edges the path actually uses.

   Example

   Path s\to a\to t uses residual capacities 2 and 3, so the bottleneck is \min(2,3)=2.

   Why: pushing more than the smallest residual capacity would violate that one edge's limit.

4. 4

   For each original edge on the path: add the bottleneck to its flow if the path used the forward residual edge, or subtract the bottleneck if it used the backward one.

   Example

   Pushing bottleneck 2 along s\to a\to t (both forward edges) updates f(s,a) from 2 to 4 and f(a,t) from 0 to 2, raising the flow's value from 2 to 4.

   Why: this is exactly the new flow f' from the definition above, and conservation holds automatically at every internal vertex.