Successive Shortest Paths for Min-Cost Flow

The min-cost flow problem: given a network with edge capacities $c(u,v)$ and edge costs $w(u,v)$, ship $d$ units of flow from a source $s$ to a sink $t$ at minimum total cost.

The Successive Shortest Paths (SSP) algorithm builds the optimal flow one path at a time:

1. Initialize $f \equiv 0$ on every edge.
2. While $|f| < d{:}$
   • Find a minimum-cost $s$-$t$ path $P$ in the residual graph $G_f.$
   • Let $\Delta = \min\!\left( d - |f|,\ \min\limits_{e \in P} r(e) \right),$ where $r(e)$ is the residual capacity of edge $e.$
   • Push $\Delta$ units along $P{:}$ the total cost increases by $\Delta \cdot c(P),$ where $c(P) = \sum\limits_{e \in P} w(e).$
   • Update $G_f.$

If at some iteration no $s$-$t$ path exists in $G_f,$ the demand is infeasible.

Residual graphs can contain negative-cost edges (introduced when previously-pushed flow is reversed), so shortest paths are computed with Bellman-Ford rather than Dijkstra.

On the first iteration the residual graph equals the original network, so we just enumerate the directed $s$-$t$ paths and pick the cheapest. The maximum amount we can push along it is the smallest capacity on the path -- the bottleneck.

For instance, in the network with edges $(u \to v{:}\ \text{cap}, \text{cost})$

$$s \to a{:}\ (3, 1), \quad s \to b{:}\ (5, 4), \quad a \to t{:}\ (4, 6), \quad b \to t{:}\ (2, 1),$$

there are two $s$-$t$ paths:

• $s \to a \to t{:}$ cost $1+6=7,$ bottleneck $\min(3,4)=3.$
• $s \to b \to t{:}$ cost $4+1=5,$ bottleneck $\min(5,2)=2.$

The cheapest is $s \to b \to t,$ along which we can push at most $2$ units.