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

Residual Networks

Understand residual capacity, forward and backward edges, and how residual graphs represent remaining flow potential.

Residual Networks

You'll learn how residual graphs track the remaining capacity for flow adjustments in a network, using forward and backward edges to represent flow potential.

What Is a Residual Network?

A residual network is a transformed version of your original flow network that shows how much more flow you can push along each edge. Think of it like a map showing available "room" for traffic on every road after some cars are already driving.

For every edge in your flow network, the residual network creates:

  • Forward edges: Show remaining capacity (original capacity minus current flow)
  • Backward edges: Allow you to "undo" flow by redirecting it elsewhere

Why Backward Edges?

Imagine you've sent 5 units of flow from A to B (capacity 10). Later, you realize it would be better to route some through C instead. The backward edge from B to A (with capacity 5) lets you conceptually "cancel" that flow and reroute it—even though real flow only moves forward.

Residual Capacity

The residual capacity c_f(u,v) tells you how much additional flow can traverse an edge:

  • If original edge (u→v) has capacity 10 and current flow 7: forward residual = 3
  • Simultaneously, backward edge (v→u) gets residual capacity = 7 (the flow you could redirect)

Together, these edges represent all possible flow adjustments: increasing flow forward or decreasing it (via the backward path).

Why It Matters

Residual networks are the foundation of flow algorithms like Ford-Fulkerson. By finding paths with available residual capacity (augmenting paths), you iteratively increase flow until no more improvements are possible.

Key Takeaway: Residual networks use forward edges (remaining capacity) and backward edges (reversible flow) to represent all possible ways to modify flow, forming the basis for maximum flow algorithms.