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

Augmenting Paths

Understand paths from source to sink in the residual network that can increase total flow.

Augmenting Paths

You'll learn: How to identify special paths in a residual network that let you push more flow from source to sink.

What Is an Augmenting Path?

An augmenting path is a path from the source node to the sink node in the residual network where every edge along the path has positive residual capacity. In simpler terms: it's a route through which you can still send more "stuff" (flow) without violating any capacity limits.

Think of it like finding an available shipping route from a warehouse to a destination. Even if some roads are at full capacity, if you can find any combination of roads (including reverse routes that let you "reroute" existing shipments) with room left, you can increase your total delivery volume.

Why Augmenting Paths Matter

The existence of an augmenting path means your current flow is not maximum — you can do better! By pushing additional flow along this path, you increase the total flow value from source to sink.

The bottleneck of an augmenting path is the smallest residual capacity among all edges in the path. This determines exactly how much additional flow you can push through that route.

The Process

  1. Look at your residual network (which shows remaining capacities)
  2. Find any path from source to sink with all positive capacities
  3. Identify the minimum capacity along that path (the bottleneck)
  4. Push that amount of flow through the entire path
  5. Update the residual network
  6. Repeat until no augmenting path exists

When no augmenting path can be found, you've reached maximum flow.

Key Takeaway: An augmenting path is a source-to-sink route in the residual network with available capacity; finding and using these paths systematically leads to computing maximum flow.