The Pipeline Detours

Part A: one unit at a time

The maximum flow is 2000: 1000 along $s\to a\to t$ and 1000 along $s\to b\to t$. Every augmentation pushes at least 1 unit, so no run takes more than 2000. The worst run takes exactly that many. It pushes 1 along $s\to a\to b\to t$, then 1 along $s\to b\to a\to t$ using the arc that sends the middle pipe's flow back, and repeats. Each path's tightest pipe is the middle one, with capacity 1. A good choice finishes in 2 augmentations.

Part B: the cautious rule walks straight into it

On part A's network with capacities 100, the smallest-bottleneck rule picks the middle path every time, since its bottleneck is 1. It alternates exactly as above: 200 augmentations for a flow of 200. Shortest augmenting paths (Edmonds–Karp) finish the same network in 2. The number of augmentations of plain Ford–Fulkerson depends on the capacities, not just on the size of the network.

Part C: augment along shortest paths, and read the cut off the end

Edmonds–Karp finds each augmenting path by breadth-first search in the residual network, including the arcs that send flow back. The distance from $s$ to every junction never decreases, and each pipe can be the bottleneck only $O(n)$ times. So there are at most $O(nm)$ augmentations whatever the capacities, even ${10}^9$.

When no augmenting path is left, let $S$ be the junctions reachable from $s$ in the residual network. Every pipe leaving $S$ is full, and every pipe entering $S$ carries nothing, otherwise something more would be reachable. So the flow's value equals the capacity of the cut $S$. That is the max-flow min-cut theorem, and it is also the certificate the grader checks. The grader never computes a maximum flow itself. It checks that your flow is feasible and that your cut's capacity equals its value.

The reverse arcs are essential. On the grader's network "a route that blocks two others", augmenting without them takes $s\to a\to b\to t$ first and is stuck at 1. The maximum is 2: send $a$'s unit on to $d$ instead, and route $c$'s through $b$.

Going further

• Ford–Fulkerson need not stop when capacities are irrational. Zwick found the smallest networks on which it runs forever, and its flow can even converge to the wrong value.
• Faster algorithms. Dinic's blocking flows take $O(n^{2}m)$. Orlin gave an $O(nm)$ algorithm. In 2022 Chen, Kyng, Liu, Peng, Probst Gutenberg and Sachdeva computed maximum flow in almost-linear time, $m^{1+o(1)}$.
• The cut as a dual. The max-flow min-cut theorem is LP duality in disguise (LP Duality): the cut is the dual solution that certifies the flow.

References

1. L. R. Ford, D. R. Fulkerson. Maximal flow through a network. Canadian Journal of Mathematics 8, 1956.
2. J. Edmonds, R. M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM 19(2), 1972.
3. U. Zwick. The smallest networks on which the Ford–Fulkerson maximum flow procedure may fail to terminate. Theoretical Computer Science 148(1), 1995.
4. J. B. Orlin. Max flows in O(nm) time, or better. Proceedings of STOC, 2013.
5. L. Chen, R. Kyng, Y. P. Liu, R. Peng, M. Probst Gutenberg, S. Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. Proceedings of FOCS, 2022.