Minimum Cost Flow

Each edge has a capacity and a cost per unit of flow. Find the cheapest way to send a required amount of flow from $s$ to $t$ — or the cheapest maximum flow (MCMF).

Successive Shortest Paths (SSP)

Repeatedly augment along the cheapest path in the residual graph.

while flow < required and an s->t path exists:
    find the minimum-cost path in the residual graph
    push as much flow along it as capacity allows

Why it is optimal: if the current flow is a minimum-cost flow of its value, augmenting along a shortest path yields a minimum-cost flow of the new value. Inductively the answer is optimal at every value — so SSP also solves the parametric problem of “cheapest flow of value $k$” for all $k$ at once.

Johnson potentials — using Dijkstra instead of Bellman-Ford

Residual graphs have negative edges (the reverse of a positive-cost edge costs $-c$), so Dijkstra cannot be used directly. Fix it with potentials:

$c^{\pi }(u,v)=c(u,v)+\pi (u)-\pi (v)\ge 0.$

Initialise $\pi$ with one Bellman-Ford run (or with zeros if all costs are non-negative), then after each Dijkstra set $\pi (v)+=d(v)$. Reduced costs stay non-negative, and the shortest paths are unchanged — the same Johnson reweighting used for all-pairs shortest paths.

struct MCMF {
    struct E { int to; long long cap, cost; };
    vector<E> es; vector<vector<int>> g;
    vector<long long> pot, dist; vector<int> pv;
    int n;
 
    MCMF(int n) : g(n), pot(n, 0), dist(n), pv(n), n(n) {}
    void addEdge(int u, int v, long long cap, long long cost) {
        g[u].push_back(es.size()); es.push_back({v, cap,  cost});
        g[v].push_back(es.size()); es.push_back({u, 0,   -cost});
    }
 
    pair<long long,long long> run(int s, int t, long long need = LLONG_MAX) {
        long long flow = 0, cost = 0;
        // if negative costs exist, initialise pot[] with Bellman-Ford here
        while (flow < need) {
            dist.assign(n, LLONG_MAX);
            priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
            dist[s] = 0; pq.push({0, s});
            while (!pq.empty()) {
                auto [d, u] = pq.top(); pq.pop();
                if (d > dist[u]) continue;
                for (int id : g[u]) {
                    auto& e = es[id];
                    if (e.cap <= 0) continue;
                    long long nd = d + e.cost + pot[u] - pot[e.to];
                    if (nd < dist[e.to]) { dist[e.to] = nd; pv[e.to] = id; pq.push({nd, e.to}); }
                }
            }
            if (dist[t] == LLONG_MAX) break;
            for (int i = 0; i < n; i++) if (dist[i] < LLONG_MAX) pot[i] += dist[i];
 
            long long push = need - flow;
            for (int v = t; v != s; v = es[pv[v] ^ 1].to) push = min(push, es[pv[v]].cap);
            for (int v = t; v != s; v = es[pv[v] ^ 1].to) {
                es[pv[v]].cap -= push; es[pv[v] ^ 1].cap += push;
                cost += push * es[pv[v]].cost;
            }
            flow += push;
        }
        return {flow, cost};
    }
};

Complexity

Method	Time
SSP with Bellman-Ford	$O(F\cdot VE)$
SSP with potentials + Dijkstra	$O(F\cdot E\log V)$
Capacity scaling SSP	$O(E^2\log V\log U)$
Cycle cancelling	$O(V{E}^{2}CU)$
Min-mean cycle cancelling	strongly polynomial
Cost scaling	$O(VE\log V\log (VC))$
Network simplex	exponential worst case, fastest in practice

$F$ is the total flow. In contest problems $F$ is usually $O(V)$ (matching-style), which makes SSP comfortably fast.

Modelling patterns

Problem	Construction
Assignment problem	$s\to L$ (cap 1, cost 0), $L\to R$ (cap 1, cost $c_{ij}$), $R\to t$ (cap 1, cost 0)
Transportation / supply-demand	supplies from $s$, demands to $t$, shipping costs on edges
$k$ vertex-disjoint paths of minimum total cost	split vertices; flow of value $k$ — see Suurballe
Minimum cost to satisfy lower bounds	circulation with demands
Scheduling with time slots	jobs on one side, slots on the other, costs = penalties
Convex cost functions	replace one edge by several parallel edges with increasing costs — the SSP order makes the cheapest get used first

That last row is important: piecewise-linear convex costs are modelled by splitting an edge into parallel edges of increasing cost, and min-cost flow handles them automatically. Non-convex costs break this and generally make the problem NP-hard.

Negative costs

Allowed, as long as there is no negative-cost cycle in the initial graph. Initialise potentials with Bellman-Ford. If negative cycles exist, first cancel them (or note that the “minimum cost flow of value 0” is already negative).

See also: Maximum Flow · Hungarian Algorithm · Circulation with Demands