Cost Skew-Symmetry, Negative Cycle Optimality & Successive Shortest Paths
For each original edge $e = (u, v)$ with capacity $c(e)$ and unit cost $w(e)$, its reverse residual partner $e^R = (v, u)$ has initial capacity $0$ and unit cost $w(e^R) = -w(e)$.
Theorem 1 (Negative-Cost Cycle Optimality Criterion): A flow $f$ of value $|f|$ has minimum cost among all flows of value $|f|$ if and only if the residual graph $G_f$ contains no directed cycle of strictly negative total cost.
Theorem 2 (Successive Shortest Path Invariant): Suppose $f$ has no negative-cost residual cycles and $\pi: V \to \mathbb{R}$ are valid node potentials satisfying $w_\pi(u, v) = w(u, v) + \pi(u) - \pi(v) \ge 0$ for all $(u, v) \in E_f$. Let $d'(u)$ be the shortest path distance from $s$ to $u$ in $G_f$ under $w_\pi$, and augment flow along a shortest $s \leadsto t$ path $P$. Then updating potentials to:
$$\pi_{\text{new}}(u) = \pi(u) + d'(u)$$guarantees $w_{\pi_{\text{new}}}(u, v) \ge 0$ for all edges in the new residual graph $G_{f'}$—including newly created reverse edges $(v, u)$ along $P$, because along $P$, $d'(v) = d'(u) + w_\pi(u, v) \implies w_{\pi_{\text{new}}}(v, u) = 0$! $\blacksquare$
Model Max-Weight Closure (Project Selection) as S-T Min-Cut with ∞ prerequisite arcs, tighten Hungarian dual potentials u_i + v_j = c_ij on the equality subgraph, or route Min-Cost Max-Flow via Johnson reduced costs.
Invariant & State
After updating $\pi[u] \mathrel{+}= d[u]$ (where $\pi[s] = 0$), what is the true unadjusted unit cost of the augmenting path $P$ from $s$ to $t$? By telescoping sum, $\sum_{e \in P} w(e) = \pi_{\text{new}}[t] - \pi_{\text{new}}[s] = \pi_{\text{new}}[t]$! You don't even need to sum edge costs along the path—simply add pushed * pi[t] to totalCost!
| MCMF Algorithm | Time Complexity | Handles Initial $w(e) < 0$? | Best Use Case |
|---|---|---|---|
| Successive Shortest Path (SPFA) | $O(|f^*| \cdot V E)$ | Yes (if no negative cycles) | Small flow $|f^*|$, general initial costs |
| SSP + Johnson Potentials + Dijkstra | $O(V E + |f^*| \cdot E \log V)$ | Yes (via 1 initial Bellman-Ford) | Standard production & CP choice |
| Primal-Dual Capacity Scaling | $O(E^2 \log U \log V)$ | Yes | Large capacities $U \gg V$ |
Production C++20 Implementation: Min-Cost Max-Flow with Johnson Potentials & Dijkstra
#include <vector>
#include <queue>
#include <algorithm>
#include <limits>
class MinCostMaxFlow {
public:
struct Arc {
int from, to;
long long cap, cost;
};
explicit MinCostMaxFlow(int n) : n(n), adj(n), pi(n, 0) {}
void addEdge(int u, int v, long long cap, long long cost) {
adj[u].push_back(static_cast<int>(arcs.size()));
arcs.push_back({u, v, cap, cost});
adj[v].push_back(static_cast<int>(arcs.size()));
arcs.push_back({v, u, 0, -cost}); // Reverse edge has negative cost!
if (cost < 0) hasNegativeInitCost = true;
}
// Optional: call or auto-triggered if initial graph has negative-cost edges (no negative cycles)
void initPotentialsBellmanFord(int s) {
std::fill(pi.begin(), pi.end(), INF);
pi[s] = 0;
for (int iter = 0; iter < n - 1; ++iter) {
bool changed = false;
for (const auto& e : arcs) {
if (e.cap > 0 && pi[e.from] < INF && pi[e.from] + e.cost < pi[e.to]) {
pi[e.to] = pi[e.from] + e.cost;
changed = true;
}
}
if (!changed) break;
}
}
std::pair<long long, long long> minCostMaxFlow(int s, int t, long long flowLimit = INF) {
if (hasNegativeInitCost) initPotentialsBellmanFord(s);
long long totalFlow = 0, totalCost = 0;
std::vector<long long> dist(n);
std::vector<int> parentArc(n);
while (totalFlow < flowLimit) {
std::fill(dist.begin(), dist.end(), INF);
std::fill(parentArc.begin(), parentArc.end(), -1);
using State = std::pair<long long, int>;
std::priority_queue<State, std::vector<State>, std::greater<State>> pq;
dist[s] = 0;
pq.emplace(0, s);
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue;
for (int id : adj[u]) {
const auto& e = arcs[id];
if (e.cap == 0) continue;
long long reducedCost = e.cost + pi[u] - pi[e.to];
if (d + reducedCost < dist[e.to]) {
dist[e.to] = d + reducedCost;
parentArc[e.to] = id;
pq.emplace(dist[e.to], e.to);
}
}
}
if (dist[t] == INF) break;
for (int i = 0; i < n; ++i) {
if (dist[i] < INF) pi[i] += dist[i];
}
long long push = flowLimit - totalFlow;
for (int cur = t; cur != s; cur = arcs[parentArc[cur]].from) {
push = std::min(push, arcs[parentArc[cur]].cap);
}
for (int cur = t; cur != s; cur = arcs[parentArc[cur]].from) {
int id = parentArc[cur];
arcs[id].cap -= push;
arcs[id ^ 1].cap += push;
}
totalFlow += push;
totalCost += push * (pi[t] - pi[s]);
}
return {totalFlow, totalCost};
}
private:
static constexpr long long INF = std::numeric_limits<long long>::max() / 4;
int n;
bool hasNegativeInitCost = false;
std::vector<Arc> arcs;
std::vector<std::vector<int>> adj;
std::vector<long long> pi;
};You must update $\pi[u] \mathrel{+}= \text{dist}[u]$ for every reachable vertex $u$ (if (dist[u] < INF)), not just vertices on the chosen $s \leadsto t$ path! If you only update $\pi$ on the path, non-path edges leaving the path will violate $w_\pi(u, v) \ge 0$ in the next iteration and corrupt Dijkstra.