Minimum-Cost Flow Residual Rerouting
Undo an earlier route through residual edges to find the cheapest multi-unit flow.
Free theory articleUndo an earlier route through residual edges to find the cheapest multi-unit flow.
Concept & interpretation
Finding the cheapest way to send multi-unit flow through a network can require routing flow sub-optimally at first, and then using residual edges to undo those early decisions as more flow is added.
Experiment
You can verify this counter-intuitive optimal routing logic by tracing the flow in the interactive module.
- Open the Minimum-Cost Flow Residual Rerouting module.
- Change the Network to "Reroute".
- Set the Demand to "2".
- Observe that the first unit flows through the cross edge, and the second unit reverses that flow, resulting in a total cost of 4.