Residual Networks
You'll learn how residual networks track remaining capacity in flow networks and enable flow adjustments for optimization.
What Is a Residual Network?
When solving the maximum flow problem, we need a way to track two things at every step:
- How much more flow can we push through each edge? (remaining capacity)
- Can we "undo" flow we've already sent? (flow reversal)
A residual network is a transformed version of your original flow network that answers both questions. For every edge in your network, the residual network shows the residual capacity—how much additional flow that edge can handle given the current flow.
How It Works
Think of it like a two-way street system:
- Forward edge: If edge (u, v) has capacity 10 and current flow 4, the residual network shows a forward edge with capacity 6 (you can push 6 more units).
- Backward edge: It also adds a reverse edge from v to u with capacity 4 (you can "cancel" up to 4 units of flow).
This backward edge is crucial! It lets the algorithm reconsider earlier decisions. If pushing flow through (u, v) turns out to block a better path, the algorithm can later reduce that flow by sending flow backward.
Why This Matters
The residual network transforms the maximum flow problem into a search problem: find paths from source to sink in the residual graph, push flow along them, and update residual capacities. Without residual networks, we couldn't safely explore different flow configurations or guarantee we'd find the optimal solution.
Key Takeaway: Residual networks represent both forward capacity (how much more flow an edge can carry) and backward capacity (how much flow can be reversed), enabling algorithms to explore and optimize flow iteratively.