The greedy idea, and where it cracks
The previous guide gave us a legal flow in a flow network: a number on every edge, never exceeding capacity, with conservation at every node except the source s and sink t. Now we want the biggest possible value. The first instinct is pure greed: find any path from s to t with spare room on every edge, push as much as the tightest edge allows, repeat until no such path exists. This is appealing, fast to picture, and — left exactly like that — wrong.
Here is the classic trap. Take a diamond: s -> a, s -> b, a -> t, b -> t each with capacity 3, plus a single middle edge a -> b with capacity 3. If greed first sends 3 units along s -> a -> b -> t, every middle and bottleneck edge fills, and now no s-to-t path has room left. Greed reports a flow of value 3 and stops. But the true maximum is 6: send 3 along s -> a -> t and 3 along s -> b -> t, never touching the middle edge at all. The early greedy choice was locally fine yet globally a blunder — exactly the greedy can fail lesson from the greedy rung, now biting us in flow.
The diagnosis is precise: once we commit a unit of flow to an edge, naive greed can never reconsider. To reach value 6 we would have to UNDO the 3 units sitting on a -> b — to say 'actually, route that flow elsewhere.' A correct algorithm needs a way to send NEW flow that also cancels OLD flow when doing so frees up a better overall routing. That single requirement — the ability to push back — is the whole reason the residual graph exists.
Building the residual graph
The residual graph, written G_f for a current flow f, is a bookkeeping copy of the network that records, for every possible move, how much more flow could travel along it right now. It has two kinds of edges, and the second kind is the clever part. For an original edge u -> v with capacity c carrying flow x, the residual graph holds a forward edge u -> v with residual capacity c - x (the room still free), AND a backward edge v -> u with residual capacity x (an amount equal to the flow currently there).
Read those two edges out loud. The forward edge says: 'this pipe still has c - x of headroom, you may add that much.' The backward edge says: 'there are x units already flowing u -> v; sending up to x units in the reverse direction v -> u doesn't violate physics — it simply CANCELS some of the flow you already committed.' Pushing along a backward residual edge is not water flowing uphill; it is an accounting move that retracts a previous decision. That is the missing 'undo' the greedy version lacked.
Augmenting along a residual path
An augmenting path is simply any path from s to t in the residual graph G_f — using forward and backward residual edges freely. Its bottleneck is the smallest residual capacity along it; call it b. We augment by pushing b units along the whole path. For each step of the path, the meaning depends on the edge type: a forward residual edge u -> v means add b to the flow on the real edge u -> v; a backward residual edge v -> u means SUBTRACT b from the flow on the real edge u -> v. Either way, b is at least 1 (in integer networks), so the value strictly increases.
Why is the result still a legal flow? Walk the conservation check at an interior node on the path. The path enters the node on one residual edge and leaves on another, and in every combination — in-forward/out-forward, in-backward/out-forward, and so on — the net change to inflow-minus-outflow at that node is exactly zero. Capacities also stay respected: a forward push of b never exceeds the residual c - x it was allowed, and a backward push of b never removes more than the x that was there. So augmentation maps a legal flow to a legal flow of strictly larger value. This is the heart of the Ford-Fulkerson method.
- Back to the diamond, after greed has stuck at value 3 with 3 units on s -> a -> b -> t. Build G_f. The edge a -> b is full, so its forward residual is gone but a backward residual edge b -> a of capacity 3 now exists.
- Find an augmenting path: s -> b (forward, room 3), then b -> a (BACKWARD, room 3 — this is the undo), then a -> t (forward, room 3). Bottleneck b = 3.
- Push 3: add 3 on real edges s -> b and a -> t, and subtract 3 on real edge a -> b (cancelling it to 0). The flow is now 3 on s -> a -> t and 3 on s -> b -> t. Value jumped from 3 to 6 — the true maximum — purely by letting one step run backward.
When do we stop, and is it right?
The method's stopping rule is wonderfully simple: keep augmenting until the residual graph has NO s-to-t path at all. The deep payoff is that this is not just 'we gave up' — it is a certificate of optimality. When no augmenting path exists, the set of nodes still reachable from s in G_f forms one side of an s-t cut, and one can show the value of the current flow exactly equals the capacity of that cut. Since every flow's value is at most every cut's capacity (weak duality, from the previous rung's spirit), matching them proves both are optimal. That equality is the max-flow min-cut theorem, the star of the next guide — augmenting paths are how we will actually prove it.
Termination needs care, and here the honesty matters. With integer capacities, every augmentation raises the value by at least 1, and the value is bounded above by the total capacity leaving s, so the loop must stop after finitely many steps — the value is a well-founded measure that cannot rise forever. But the generic Ford-Fulkerson method does NOT promise a fast number of steps: if you choose augmenting paths carelessly, you can need a number of augmentations proportional to the maximum flow value itself. On a graph with capacities like 1000000, an adversary can force you to crawl up by tiny increments, one unit at a time.
Edmonds-Karp, Dinic, and what the path choice buys
The first fix is almost embarrassingly clean. Edmonds-Karp is Ford-Fulkerson with one rule: always pick the augmenting path with the FEWEST edges — that is, a shortest path in edge count, found by a plain breadth-first search in the residual graph. With this single discipline, one can prove the number of augmentations is at most O(V*E), independent of the capacity values. Each BFS costs O(E), so the whole algorithm runs in O(V*E^2). Capacities have completely vanished from the bound — the pathological slowness above is gone simply because BFS never wastes augmentations on roundabout paths.
Why does shortest-first work? The key lemma is that the BFS distance from s to t in the residual graph never DECREASES as the algorithm runs, and strictly increases often enough that the total augmentation count is bounded. The proof is a careful look at how a backward edge can reappear, and it is one of the prettier counting arguments in the whole subject. You do not need to carry the proof in your head to use the algorithm, but it is worth knowing the speedup is earned by an honest invariant, not luck.
Dinic's algorithm pushes the same idea further and is what you would reach for in practice. Instead of one shortest path at a time, each phase first runs a BFS to compute the level graph — the layering of nodes by distance from s — then finds a blocking flow in that layered graph, saturating many shortest paths at once before re-running BFS. This collapses the per-phase work and yields O(V^2 * E) in general, improving to O(E * sqrt(V)) on unit-capacity networks — the bound that makes flow-based bipartite matching, two guides from now, genuinely fast. Same residual graph, same augmenting-path principle; only the scheduling of the pushes grows more clever.
One closing caution in the spirit of this whole ladder: those bounds are worst-case asymptotics, and the usual hidden-constant caveats apply. On real, structured inputs all three methods often finish far faster than their guarantees, and a 'slower' bound can win on a particular family of graphs. The point of three names is not a strict ranking but a menu: the residual graph is the one idea, and which augmenting paths you choose — any, shortest, or a whole blocking layer — trades implementation effort against a provable worst case.