Minimum-Cost Flow Residual Rerouting

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.

Worked Example: Rerouting Flow

To route 2 units in the Reroute network, we use successive shortest augmenting paths.

The first unit takes the shortest path s0 → v1 → v2 → t3 (cost: 1 + (-1) + 1 = 1).
This path saturates the cross edge (v1, v2) with capacity 1 and cost -1. In the residual network, a reverse edge (v2, v1) is created with cost 1.
The second unit takes the shortest residual path s0 → v2 → v1 → t3 (cost: 1 + 1 + 1 = 3), effectively rerouting the flow.
Total cost for 2 units is 1 + 3 = 4.

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.

Limitations

This module demonstrates a specific scenario with four vertices, discrete demand up to 3 units, and fixed capacity bounds. It expects integer capacities and costs, and does not dynamically solve arbitrary generic network topologies or multi-source/multi-sink formulations.

References

This MIT reference supports the algorithmic logic of successive shortest augmenting paths in finding minimum-cost flow.

Minimum-Cost Flow Residual Rerouting