Running Ford–Fulkerson
A flow network is a directed graph with a designated source \(s\), a distinct sink \(t\), and a nonnegative capacity on each arc. Ford–Fulkerson repeatedly looks for a route from \(s\) to \(t\) along which more flow can be sent. The route is found in the residual network: it records not only unused capacity on original arcs, but also opportunities to undo flow sent earlier.
All networks below are directed and have no parallel or oppositely directed original arcs. A flow \(f\) assigns a number \(f(u,v)\) to each original arc \(u\to v\). It is feasible if \(0\le f(u,v)\le c(u,v)\) on every arc and, at each vertex other than \(s,t\), total inflow equals total outflow. Its value \(|f|\) is the net outflow from \(s\).
When an augmenting path is chosen, let \(\delta\) be its bottleneck. For each forward residual arc \(u\to v\), increase the flow on its corresponding original arc by \(\delta\). For each reverse residual arc \(v\to u\), decrease the flow on the corresponding original arc \(u\to v\) by \(\delta\). The reverse arc therefore represents cancellation, not additional flow in the original direction.
Why an Augmentation Is Valid
Proof. Consider an original arc used forward by \(P\). Its residual capacity is \(c-f\), so \(\delta\le c-f\). Increasing its flow to \(f+\delta\) keeps it at most \(c\), and it remains nonnegative. If \(P\) uses the reverse residual arc for an original arc with flow \(f\), then \(\delta\le f\); decreasing that flow to \(f-\delta\) keeps it nonnegative and does not increase it beyond its capacity. Arcs not represented on \(P\) are unchanged.
At each internal vertex, the residual path has one arc entering and one leaving. Each residual-arc update changes the original flow so that it increases net outflow at the residual arc’s tail by \(\delta\) and decreases net outflow at its head by \(\delta\). Thus the two changes cancel at every internal vertex, preserving conservation. Since the path is simple, it meets \(s\) only at its start and \(t\) only at its end. The update increases net outflow at \(s\) by \(\delta\), so \(|f'|=|f|+\delta\). Therefore \(f'\) is feasible and has the stated value. \(\square\)
This proposition explains why the path update works, including when the path contains reverse residual arcs. The method starts from the zero flow, repeatedly performs such an update, and stops when no augmenting path is available. The worked examples below give finite executions and check their flows; they do not rely on a general termination or optimality theorem.
Worked Executions
Worked Example: A Path That Cancels Earlier Flow
Let \(V=\{s,a,b,t\}\), with source \(s\), sink \(t\), and directed arcs with capacities \(s\to a:3,\ s\to b:2,\ a\to b:2,\ a\to t:2,\ b\to t:3\). Begin with zero flow on every arc. In the tables, each entry is “flow; forward residual / reverse residual.” The reverse residual is placed on the arc opposite the original one.
First choose \(P_1=s\to a\to b\to t\). Its residual capacities are \(3,2,3\), so \(\delta_1=\min(3,2,3)=2\). Increase the flow on all three original arcs by \(2\). The flow value becomes \(0+2=2\).
| Original arc | After \(P_1\): flow; forward / reverse residual |
|---|---|
| \(s\to a\), capacity 3 | \(2;\ 3-2=1\ /\ 2\) |
| \(s\to b\), capacity 2 | \(0;\ 2-0=2\ /\ 0\) |
| \(a\to b\), capacity 2 | \(2;\ 2-2=0\ /\ 2\) |
| \(a\to t\), capacity 2 | \(0;\ 2-0=2\ /\ 0\) |
| \(b\to t\), capacity 3 | \(2;\ 3-2=1\ /\ 2\) |
Next choose \(P_2=s\to a\to t\). Its residual capacities are \(1\) and \(2\), giving \(\delta_2=\min(1,2)=1\). The flows on \(s\to a\) and \(a\to t\) become \(2+1=3\) and \(0+1=1\). The value is \(2+1=3\). At this stage the flows on \(s\to a,s\to b,a\to b,a\to t,b\to t\), in that order, are \(3,0,2,1,2\); their forward/reverse residual pairs are \(0/3,\ 2/0,\ 0/2,\ 1/1,\ 1/2\).
Now choose \(P_3=s\to b\to a\to t\). The middle step \(b\to a\) is the reverse residual arc for the original arc \(a\to b\). The residual capacities on this path are \(2,2,1\), so \(\delta_3=\min(2,2,1)=1\). Increase \(f(s,b)\) from \(0\) to \(1\), decrease \(f(a,b)\) from \(2\) to \(1\), and increase \(f(a,t)\) from \(1\) to \(2\). The new flow value is \(3+1=4\).
The updated flows, in the same arc order, are \(3,1,1,2,2\), with forward/reverse residual pairs \(0/3,\ 1/1,\ 1/1,\ 0/2,\ 1/2\). Finally take \(P_4=s\to b\to t\), whose residual capacities are \(1\) and \(1\). Thus \(\delta_4=\min(1,1)=1\). The final flows are \(3,2,1,2,3\), and the value is \(4+1=5\). The final forward/reverse residual pairs are \(0/3,\ 0/2,\ 1/1,\ 0/2,\ 0/3\). Both arcs leaving \(s\) have zero forward residual capacity, so there is no residual path starting at \(s\); this execution stops.
Check: The final flow satisfies conservation at \(a\): inflow \(3\) equals outflow \(1+2=3\). At \(b\), inflow \(2+1=3\) equals outflow \(3\). The source sends \(3+2=5\), and the sink receives \(2+3=5\), confirming the flow value. All final arc flows lie between zero and their listed capacities.
Worked Example: Three Augmentations Through a Network
Let \(V=\{s,u,v,w,t\}\), with source \(s\), sink \(t\), and arcs \(s\to u:4,\ s\to v:3,\ u\to v:2,\ u\to w:2,\ v\to w:2,\ v\to t:3,\ w\to t:4\). Start with zero flow.
Choose \(P_1=s\to u\to w\to t\). Its residual capacities are \(4,2,4\), so \(\delta_1=\min(4,2,4)=2\). The flows on \(s\to u,u\to w,w\to t\) become \(2,2,2\), and the value becomes \(2\). The forward/reverse residual pairs for those arcs are respectively \(2/2,\ 0/2,\ 2/2\); the other arcs still have their full forward capacities \(3,2,2,3\) and zero reverse residual.
Choose \(P_2=s\to v\to t\). The residual capacities are \(3,3\), so \(\delta_2=\min(3,3)=3\). The flows on \(s\to v\) and \(v\to t\) become \(3\) and \(3\); the total value is \(2+3=5\). Their residual pairs are \(0/3\) and \(0/3\).
For a third augmentation choose \(P_3=s\to u\to v\to w\to t\). The residual capacities are \(2,2,2,2\), so \(\delta_3=\min(2,2,2,2)=2\). The resulting flow values on \(s\to u,s\to v,u\to v,u\to w,v\to w,v\to t,w\to t\), in that order, are \(4,3,2,2,2,3,4\). The new flow value is \(5+2=7\).
The final forward/reverse residual pairs in that same order are \(0/4,\ 0/3,\ 0/2,\ 0/2,\ 0/2,\ 0/3,\ 0/4\). In particular, neither original arc leaving \(s\) has positive forward residual capacity, so no further augmenting path can start at \(s\).
Check: At \(u\), inflow \(4\) equals outflow \(2+2=4\). At \(v\), inflow \(3+2=5\) equals outflow \(2+3=5\). At \(w\), inflow \(2+2=4\) equals outflow \(4\). The source outflow is \(4+3=7\), and the sink inflow is \(3+4=7\). These independent totals agree with the accumulated value \(2+3+2=7\).
Worked Example: A Bottleneck Away from the Source
Let \(V=\{s,a,b,t\}\), with source \(s\), sink \(t\), and arcs \(s\to a:5,\ a\to t:3,\ s\to b:4,\ b\to t:4,\ a\to b:2\). Initialize all flows to zero. Choose \(P_1=s\to a\to t\). Its residual capacities are \(5\) and \(3\), so \(\delta_1=\min(5,3)=3\). This saturates \(a\to t\), even though \(s\to a\) still has residual capacity \(5-3=2\). The flow value is \(3\).
Next choose \(P_2=s\to b\to t\). Both residual capacities are \(4\), so \(\delta_2=\min(4,4)=4\). The flow value becomes \(3+4=7\). The current flows on \(s\to a,a\to t,s\to b,b\to t,a\to b\) are \(3,3,4,4,0\).
There is no augmenting path. From \(s\), the only available outgoing residual arc is \(s\to a\), with capacity \(2\). From \(a\), the arc \(a\to t\) has residual capacity \(3-3=0\), while \(a\to b\) has residual capacity \(2-0=2\). From \(b\), the arc \(b\to t\) has residual capacity \(4-4=0\). Hence these routes cannot reach \(t\). The reverse residual arcs \(a\to s,\ t\to a,\ b\to s,\ t\to b\) point back toward \(s\) or away from it and do not create another route to \(t\).
Check: Conservation holds at \(a\), since its inflow and outflow are both \(3\), and at \(b\), since its inflow and outflow are both \(4\). The source sends \(3+4=7\), matching the sink’s \(3+4=7\) inflow. Each flow is within capacity. Thus the recorded feasible flow has value \(7\), and the procedure stops because no residual \(s\)-\(t\) path exists.
Common Mistakes and the Stopping Rule
Treating a reverse residual arc as an original arc. In the first example, before \(P_3\) the original arc \(a\to b\) already carries \(2\), its capacity. The path uses the reverse residual arc \(b\to a\) with bottleneck \(1\). The correct update reduces \(f(a,b)\) from \(2\) to \(2-1=1\). If one incorrectly increases it to \(2+1=3\), the capacity bound \(f(a,b)\le2\) is violated. The error also breaks conservation at \(a\): the supposed outflow would be \(3+2=5\), while its inflow is only \(3\). Always identify which original arc a residual arc represents before changing a flow.
Using a path that is not available. Every arc of an augmenting path must have positive residual capacity. A large capacity on one arc does not compensate for a zero residual capacity on another. The bottleneck is the minimum over the whole path, not a sum or an average.
Confusing the stopping condition with a proof of optimality. The execution stops when there is no residual path from \(s\) to \(t\). The examples verify this condition directly where stated. Establishing the general relationship between this condition and maximum flows belongs to the later augmenting-path characterization. Likewise, a sequence of valid augmentations alone does not establish that the procedure must terminate for every possible choice of capacities.
Set every original-arc flow to zero and compute its forward and reverse residual capacities.
Choose a path from \(s\) to \(t\) using only positive-residual-capacity arcs. Record the direction of each arc and the original arc it represents.
Take the minimum residual capacity on the path and update original flows by increasing on forward residual arcs and decreasing on reverse residual arcs.
Recompute residual capacities, check conservation and flow value, then search again. Stop when no residual \(s\)-\(t\) path is available.
Check Your Understanding
For each question, distinguish original arcs from residual arcs and show the arithmetic supporting your answer.
- For an original arc of capacity \(6\) carrying flow \(4\), what are its forward and reverse residual capacities?
- If an augmenting path has residual capacities \(5,2,4\), what is its bottleneck, and by how much does the flow value increase?
- Explain why using a reverse residual arc can reduce flow on an original arc without violating conservation.
- In the third worked example, why is the remaining forward residual capacity on \(s\to a\) insufficient to give another augmentation?
- State the stopping condition used in these executions. Does that condition alone prove the flow is maximum in this tutorial?