Minimum-Cost Maximum Flow

Why “Cheapest” Changes the Flow Problem

A maximum-flow algorithm treats all feasible routes as interchangeable: if two routes can each carry one unit, either is equally useful. Real systems do not work that way. One shipping lane may be slower, one worker–shift pairing may be less desirable, and one data route may consume more bandwidth. Minimum-cost maximum flow (MCMF) keeps the capacity logic of maximum flow while attaching a price to every unit that crosses an edge.

The Optimization Model

For every directed edge $(u,v)$, let $c(u,v)$ be its capacity, $w(u,v)$ its cost per unit, and $f(u,v)$ the chosen flow. A legal solution satisfies two kinds of constraints:

The value $|f|$ is the net amount leaving the source. MCMF uses a lexicographic objective: first maximize $|f|$; among all maximum flows, choose one with minimum total cost:

Residual Edges Are an Undo Button

The residual network records what the algorithm may change next. If an original edge has capacity $c$, cost $w$, and currently carries flow $f$, its residual representation contains:

Successive Shortest Augmenting Paths

The successive shortest augmenting path method turns optimization into repetition. At each round it asks: “Given everything I can still add or undo, what is the cheapest way to send the next batch from $s$ to $t$?”

flowchart LR
    S[Residual network] --> P[Cheapest s-to-t path]
    P --> B[Path bottleneck]
    B --> U[Push and update]
    U --> S

1. Build or maintain the residual graph.
2. Find a minimum-cost residual path from $s$ to $t$.
3. Let $\Delta$ be the smallest residual capacity on that path.
4. Push $\Delta$ units, subtracting it from forward residual capacities and adding it to reverse capacities.
5. Stop when $t$ is unreachable or when the requested demand has been delivered.

The bottleneck matters because one shortest-path search can often ship several units. That makes the number of rounds depend on the structure of the capacities, not simply on the number of edges.

A Worked Network, One Augmentation at a Time

Edge labels below use capacity · cost per unit. The highlighted route is the cheapest initial path: $s \to A \to B \to t$, with unit cost $1+0+1=2$ and bottleneck $1$.

After round 3, all three units of source capacity are used, so the maximum flow is $3$. The minimum cost among flows of that value is $9$. Notice the accounting pattern: each row adds push × unit cost to the running total.

Potentials Make Dijkstra Legal Again

Reverse edges can have negative cost, and ordinary Dijkstra is not correct on graphs with negative edge weights. Potentials repair that problem without changing which $s$-$t$ path is cheapest.

Maintain a potential $\pi(v)$ for each vertex and replace each residual cost with a reduced cost:

Every $s$-$t$ path gains the same telescoping offset, $\pi(s)-\pi(t)$. Therefore, comparing reduced path costs gives the same ordering as comparing original path costs.

Why does the update keep reduced costs nonnegative? Dijkstra’s distances obey $d(v) \le d(u)+\widehat{w}(u,v)$. Rearranging gives $\widehat{w}(u,v)+d(u)-d(v) \ge 0$, which is exactly the new reduced cost.

Why the Method Works

The full proof is a primal–dual argument, but its core can be understood through three invariants:

Reverse edges are what connect the last two ideas. Any alternative flow of the same value differs from the current flow by residual cycles. If none of those cycles has negative cost, no alternative can be cheaper. When no residual $s$-$t$ path remains, the flow is also maximum.

Implementation: Separate the Four Responsibilities

A robust solver is easier to reason about when four jobs stay distinct: edge insertion creates paired forward/reverse edges, shortest-path search records a parent edge for every vertex, augmentation updates both residual directions, and accounting updates total flow and cost.

from heapq import heappop, heappush

def cheapest_path(graph, source, sink):
    distance = [float("inf")] * len(graph)
    parent = [None] * len(graph)
    distance[source] = 0
    queue = [(0, source)]
    while queue:
        cost, vertex = heappop(queue)
        if cost != distance[vertex]:
            continue
        for target, capacity, edge_cost in graph[vertex]:
            if capacity and cost + edge_cost < distance[target]:
                distance[target] = cost + edge_cost
                parent[target] = vertex
                heappush(queue, (distance[target], target))
    return distance[sink], parent

graph = [[(1, 2, 1), (2, 2, 3)], [(3, 2, 2)], [(3, 2, 1)], []]
print(cheapest_path(graph, 0, 3)[0])  # 3

#include <iostream>
#include <queue>
#include <tuple>
#include <vector>
using namespace std;

int main() {
    vector<vector<tuple<int, int, int>>> graph(4);
    graph[0] = {{1, 2, 1}, {2, 2, 3}};
    graph[1] = {{3, 2, 2}}; graph[2] = {{3, 2, 1}};
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> queue;
    vector<int> distance(4, 1e9); distance[0] = 0; queue.push({0, 0});
    while (!queue.empty()) {
        auto [cost, vertex] = queue.top(); queue.pop();
        if (cost != distance[vertex]) continue;
        for (auto [target, capacity, edgeCost] : graph[vertex])
            if (capacity && cost + edgeCost < distance[target])
                distance[target] = cost + edgeCost, queue.push({distance[target], target});
    }
    cout << distance[3] << "\n"; // 3
}

import java.util.*;

public class MinCostPath {
    record Edge(int target, int capacity, int cost) {}
    public static void main(String[] args) {
        List<List<Edge>> graph = List.of(
            List.of(new Edge(1, 2, 1), new Edge(2, 2, 3)),
            List.of(new Edge(3, 2, 2)), List.of(new Edge(3, 2, 1)), List.of());
        int[] distance = {0, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE};
        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        queue.add(new int[]{0, 0});
        while (!queue.isEmpty()) {
            int[] current = queue.remove();
            if (current[0] != distance[current[1]]) continue;
            for (Edge edge : graph.get(current[1])) if (edge.capacity() > 0 && current[0] + edge.cost() < distance[edge.target()]) {
                distance[edge.target()] = current[0] + edge.cost();
                queue.add(new int[]{distance[edge.target()], edge.target()});
            }
        }
        System.out.println(distance[3]); // 3
    }
}

In each round, save the exact parent edge, not merely the parent vertex; parallel edges may connect the same two vertices. Reconstruct the path from $t$ to $s$, find its minimum residual capacity, then update every chosen edge and its paired reverse edge.

Where the Model Pays Off

MCMF is most natural when resources are divisible into units, constraints can be expressed as edge capacities, and preferences add linearly as per-unit costs.

Assignment as a flow network

Create edges $s \to$ worker with capacity $1$ and cost $0$, worker $\to$ job with capacity $1$ and a preference cost, and job $\to t$ with capacity $1$ and cost $0$. Maximum flow assigns as many workers as possible; minimum cost chooses the best available pairing among those maximum assignments. This construction also explains why the Hungarian algorithm is a specialized alternative for balanced one-to-one assignment.

Complexity and Limits

Let $A$ be the number of augmentations. With potentials and a binary-heap Dijkstra, the main loop costs:

If capacities are integers, every augmentation sends at least one unit, so $A \le F$ for final flow value $F$. This gives the familiar worst-case bound $O(FE\log V)$, plus up to $O(VE)$ for a Bellman–Ford initialization when negative original costs exist. Memory usage is $O(V+E)$ after including reverse edges.

Choosing the Right Flow Tool