A flow is an assignment of a number to every arc that respects capacities and conserves at every interior vertex. Raise its value by finding a path from source to sink with spare capacity and pushing the bottleneck along it. The whole subject turns on one detail: the path may also run backwards along an arc that already carries flow, and without that the method stops below the maximum.
Core ideas
The hard idea is the backward arc. The definition and the residual network exist to make it expressible.
Every arc carries a number between 0 and its capacity, and at every vertex other than the source and the sink the total in equals the total out. The value of the flow is what leaves the source. The lab checks both constraints on whatever it produces and reports a verdict per vertex, so “this is a flow” is a measured statement rather than an assumption.
For each arc carrying f out of a capacity c, the residual network holds a forward arc of capacity c - f, meaning how much more can be pushed, and a backward arc of capacity f, meaning how much of the existing flow can be taken back. A path from source to sink in that network is an augmenting path, and the bottleneck is the smallest residual capacity on it.
On the lab's opening network the first-found rule takes a path through the middle arc, pushes 1, and then cannot find a second path at all — the value stops at 1. With backward arcs available the same rule finds a second path that runs backwards along the middle arc, and reaches 2. The stuck flow is a perfectly legal flow; it is maximal, in that nothing can be added to it under that restriction, and it is not maximum.
The material
The two constraints, the residual network, the augmenting step, the failure without backward arcs, and what the path rule costs.
Given a digraph with a non-negative capacity c(a) on every arc, a source s and a sink t, a flow assigns to each arc a number f(a) with 0 ≤ f(a) ≤ c(a), such that at every vertex other than s and t the total on incoming arcs equals the total on outgoing ones. Its value is the net amount leaving s.
For a flow f, the residual network has, for each arc a from u to v, a forward arc from u to v of capacity c(a) - f(a) and a backward arc from v to u of capacity f(a). Arcs of residual capacity 0 are omitted. An augmenting path is any path from s to t in it, and its bottleneck is the least residual capacity along it.
Pushing the bottleneck along an augmenting path — adding it on each forward arc and subtracting it on each backward one — produces a flow again, whose value is higher by the bottleneck. Capacities hold because the bottleneck was the minimum, and conservation holds because each interior vertex of the path gains the same amount on one side as the other.
The lab opens on 1>2 1, 1>3 1, 2>3 1, 2>4 1, 3>4 1 with source 1 and sink 4, and with backward arcs switched OFF. The first-found rule takes the three-arc path 1>2, 2>3, 3>4, pushes its bottleneck of 1, and then finds nothing: the search reaches only vertices 1 and 3, although the arc 1>3 still has spare capacity. The value stops at 1. Switch the backward arcs on and the same rule finds 1>3, then backwards along 2>3, then 2>4, pushes 1 more, and reaches 2.
Look at what the second path does. It sends a new unit from 1 to 3, cancels the unit that was going 2 to 3, and sends that one on to 4 instead. The net effect is two units arriving at the sink by two disjoint routes, and it was reachable only by rewriting a decision the first path had made. That is why the backward arc is part of the algorithm and not a refinement of it.
The stuck flow is worth naming precisely. It satisfies both constraints — the lab confirms conservation at every interior vertex — and no more can be pushed without taking something back. It is MAXIMAL. The maximum is 2. Two words that differ by three letters and by the whole content of this module.
The failure above was exhibited with a RULE rather than with a hand-picked path, and that matters: it is a claim about what an implementation does, not about what an adversary could do. On the same network the shortest-path rule happens never to take the middle arc, so it reaches 2 even with backward arcs off. That does not rescue the forward-only method, it just means this network does not defeat that particular rule.
On 1>2 100, 1>3 100, 2>3 1, 2>4 100, 3>4 100 both rules reach the maximum of 200, and they take different numbers of steps to do it. The shortest-path rule augments twice, by 100 each time. The first-found rule augments four times, by 1, then 99, then 1, then 99: it walks into the thin arc, pays for it with a backward arc later, and does it twice.
That is the case the choice of rule is usually justified by, and the lab lets you watch it rather than describing it. The shortest-path rule — always take an augmenting path with the fewest arcs — is the one the kit's own maximum-flow routine uses, and its augmentation count on this network is the one the panel reports.
On the six-vertex network with capacities from 4 to 20, the shortest-path rule reaches 23 in three augmentations, pushing 12, then 4, then 7. Three numbers that add to the answer, and the third path is four arcs long where the first two were three — the rule takes the shortest available, and what is available changes as the residual network does.
Measured against proved, and this lesson is where the two are furthest apart. Three augmentations reaching 23 is a measurement. That 23 cannot be beaten is not something any number of augmentations can establish, because stopping means only that this search found no path. “Max Flow and Min Cut” supplies the missing half, and it is the one place on this course where the algorithm hands back its own proof.
Interactive
The residual network carries the flow already sent, so a later path can take it back
Method
Build the residual network first; the search is then an ordinary reachability question.
For every arc write its spare capacity forwards and its current flow backwards, and omit anything at 0. Doing the search on the original network with the flow in your head is where the backward arcs get lost, and losing them does not look like an error — it looks like being finished.
The amount pushed is the smallest residual capacity on the path, added on forward arcs and subtracted on backward ones. Pushing different amounts on different arcs breaks conservation, and pushing more than the minimum breaks a capacity.
Both constraints, every arc and every interior vertex. It is Θ(V + E) and it catches a sign error on a backward arc immediately, which is the mistake that otherwise survives until the final value is compared with something.
“My search found no path” and “no augmenting path exists” are the same statement only if the search was on the full residual network. The lab's opening preset is the case where they differ, and the honest report at this point is a value plus the rule that produced it.
The network is 1>2 1, 1>3 1, 2>3 1, 2>4 1, 3>4 1, every capacity 1, source 1 and sink 4. The rule is first-found, which takes arcs in the order they were typed.
The forward-only run ends with the source's own arcs not both full: 1>3 still has its whole unit of spare capacity. That is the signature of being stuck rather than finished, and it is visible without knowing the answer — a maximum flow in this network would have to saturate one side of every cut, and the source's two arcs are a cut.
The last three lines are the reason the failure was demonstrated with a rule. The shortest-path rule never enters the middle arc here, so it does not need to undo anything on this particular network. A reader who saw only that rule would conclude the backward arcs are optional, and on a slightly larger network they would be wrong.
For a faded rehearsal, raise the capacity of 2>3 from 1 to 5 and predict what the first-found rule does with backward arcs off. The supplied first move is this: the first path is still 1>2, 2>3, 3>4 and its bottleneck is still 1, because 1>2 and 3>4 are unchanged. Say whether the run still stops at 1, and then say what happens if you raise 1>2 to 5 as well.
You should be able to build a residual network from a flow, find a path in it, push the bottleneck with the right sign on each arc, verify both constraints afterwards, and say precisely why a run that finds no further path has not yet established that its value is the maximum.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.