An Augmenting Path - Max-Flow, Min-Cut

The core idea of Ford-Fulkerson is local and constructive: if there is a source-to-sink path with spare capacity, push more flow on it. The path's bottleneck determines the safe amount to add, so feasibility is preserved edge by edge. This lesson shows the first deterministic augmentation in the flagship network.

highlighted = computed this step

Augmenting path

The first augmenting path is s to a to t and it uses 2 edges. An augmenting path is not just any route: every edge on it must still have spare capacity. Why: only such a route can carry additional source-to-sink flow without violating a capacity limit.

s\to a\to t

Bottleneck

The bottleneck on that path is 1. The path can only be pushed as far as its tightest edge allows. Why: adding more than the bottleneck would overfill at least one arc, while adding exactly the bottleneck keeps the whole path feasible.

\Delta=1

Pushed flow

After this push, the total s to t flow is 1. This is the first improvement from the all-empty flow. Why: augmenting adds the bottleneck amount along a complete source-to-sink route, so the total arriving at the sink rises by that same amount.

|f|=1

Diagram note

Highlighted edges are the recomputed first augmenting path; labels show exact flow over capacity. The diagram is a worked state of the algorithm, not an authored guess about where flow should go. Pixel positions are rounded for layout; every number shown is exact.

\text{one augmenting path increases flow}