Course contentsShow
← Computer Science
Lesson 1029 of 2,87224. Minimum Spanning Trees and Network FlowFree lesson

Residual Capacity of a Path

Calculate the bottleneck capacity along an augmenting path, determining how much flow can be added.

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):

  1. Look at each edge's residual capacity
  2. Find the minimum value
  3. 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.