Residual Capacity of a Path
What you'll learn: How to determine the maximum amount of flow you can push through an augmenting path in a flow network.
The Bottleneck Concept
When you've identified an augmenting path from source to sink in a residual network, you can't just push unlimited flow through it. Each edge along the path has a residual capacity—the maximum additional flow it can handle. The residual capacity of the entire path is the smallest (minimum) residual capacity among all edges on that path.
Think of it like a water pipe system: if you have pipes with capacities of 10, 5, and 8 liters per second connected in series, water can only flow as fast as the narrowest pipe allows—5 liters per second. That narrow pipe is the bottleneck.
Calculating Residual Capacity
For an augmenting path P = (s → v₁ → v₂ → ... → t):
- Look at each edge's residual capacity
- Find the minimum value
- That's how much flow you can add along this path
Formula:
residual_capacity(P) = min { residual_capacity(e) : e is an edge in P }
Why This Matters
The residual capacity tells you exactly how much flow to add when augmenting. After pushing this amount:
- At least one edge becomes saturated (residual capacity drops to zero)
- No edge is over-capacity (constraints remain valid)
- The total flow increases by this amount
Key Takeaway: The residual capacity of an augmenting path is the minimum residual capacity among all its edges—this bottleneck value determines how much flow can be safely pushed through the path.