Controls
Running Totals
Total Flow0
Total Cost0
Augmentation #0
Last Path Cost—
Last Bottleneck—
Vertex Potentials h[v]
How To Read This
Each Step runs one Successive-Shortest-Path iteration:
1. Dijkstra finds the cheapest
s→t path using
reduced costs c + h[u] − h[v].2. Potentials
h[v] are updated by the shortest
distances so every residual edge stays non-negative.3. The full bottleneck is pushed along the path; flow
and total cost update.
The run stops when no
s→t path remains — that is the
min-cost maximum flow (expected: flow 5, cost 17).Legend
Source (s)
Sink (t)
Current cheapest augmenting path
Saturated edge (flow = cap)
Residual edge with spare capacity