Minimum-Cost Flow
Before reading this article, read the definitions in Introduction to Network Flow.
Minimum-cost flow
Consider a network \(G=(V,E)\) in which every edge has, besides its capacity \(c(u,v)\), a cost \(w(u,v)\) per unit of flow.
Sending a flow of \(f(u,v)\) along \((u,v)\) costs \(f(u,v)\times w(u,v)\).
The cost \(w\) is skew-symmetric as well, that is, \(w(u,v)=-w(v,u)\).
A maximum flow of minimum total cost in this network is called a minimum-cost maximum flow: among the flows that maximize \(\sum_{(s,v)\in E}f(s,v)\), it minimizes \(\sum_{(u,v)\in E}f(u,v)\times w(u,v)\).
SSP algorithm
The successive shortest paths (SSP) algorithm is greedy: it repeatedly finds an augmenting path of minimum unit cost and augments along it, until the graph has no augmenting path left.
If the graph contains a cycle of negative unit cost, the SSP algorithm fails to find the minimum-cost maximum flow of the network. In that case, first remove the negative cycles with the cycle-canceling algorithm.
Proof
We prove that the SSP algorithm is correct by mathematical induction and proof by contradiction.
Let \(f_i\) be the minimum cost of a flow of value \(i\). Assume that the initial network has no negative cycle; then \(f_0=0\).
Suppose the value \(f_i\) computed by the SSP algorithm is the minimum cost. Starting from \(f_i\), we find a shortest augmenting path and obtain \(f_{i+1}\), so \(f_{i+1}-f_i\) is the length of this shortest augmenting path.
Suppose a smaller value of \(f_{i+1}\) exists, and call it \(f'_{i+1}\). Since \(f_{i+1}-f_i\) already comes from a shortest augmenting path, \(f'_{i+1}-f_i\) must correspond to an augmenting path that passes through at least one negative cycle.
This is a contradiction: if some augmenting path passes through at least one negative cycle, then \(f_i\) is not the minimum cost, because sending flow around that negative cycle gives a cost below \(f_i\) without increasing the flow out of \(s\).
Hence the SSP algorithm correctly finds the minimum-cost maximum flow of a network without negative cycles.
Time complexity
If shortest paths are found with the Bellman–Ford algorithm, each search for an augmenting path takes \(O(nm)\) time. Let \(f\) be the value of the maximum flow of the network; the worst-case time complexity is then \(O(nmf)\). In fact, the SSP algorithm runs in pseudo-polynomial time.
Why is the SSP algorithm pseudo-polynomial?
The running time of the SSP algorithm is bounded above by \(O(nmf)\), which is a polynomial in the value range, so the algorithm is pseudo-polynomial.
There are networks2 with \(m=n^2\) and \(f=2^{n/2}\) on which the SSP algorithm takes \(O(n^3 2^{n/2})\) time, so it is not a polynomial-time algorithm.
Implementation
Take the Edmonds–Karp algorithm or Dinic's algorithm and replace the search for an augmenting path with a shortest-path algorithm that finds an augmenting path of minimum unit cost.
Implementation based on the Edmonds–Karp algorithm
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | |
Implementation based on Dinic's algorithm
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | |
Primal-dual algorithm
Finding shortest paths with Bellman–Ford takes \(O(nm)\) time, slower than Dijkstra's algorithm1 on sparse and dense graphs alike. But the network has edges of negative unit cost, so Dijkstra's algorithm cannot be used directly.
The primal-dual algorithm works along the same lines as Johnson's all-pairs shortest paths algorithm: it gives every vertex a potential that makes the costs of all edges of the network (called edge weights below) non-negative, so that Dijkstra's algorithm can find an augmenting path of minimum unit cost.
First run a shortest-path algorithm once to find the shortest distance \(h_i\) from the source to every vertex; this is also the initial potential of the vertex. Then, as in Johnson's algorithm, reset the weight of every edge from \(u\) to \(v\) with unit cost \(w\) to \(w+h_u-h_v\).
With these potentials, the shortest paths in the new network correspond to the shortest paths in the original network. The proof was given in the description of Johnson's algorithm and is not repeated here.
Unlike in an ordinary shortest-path problem, the graph changes after every augmentation, and the potentials of the vertices then have to be updated.
How? We state the result first. Let \(d'_i\) be the shortest distance from the source to vertex \(i\) after the augmentation (measured with the reset edge weights); it suffices to add \(d'_i\) to \(h_i\). We now prove that with the edge weights updated in this way, every edge of the graph has non-negative weight.
After a round of augmentation, some edges \((i,j)\) lie on the augmenting path, so the residual network gains the corresponding edges \((j,i)\). They must satisfy \(d'_i+(w(i,j)+h_i-h_j)=d'_j\) (otherwise \((i,j)\) would not be on the augmenting path). Rearranging gives \(w(j,i)+(h_j+d'_j)-(h_i+d'_i)=0\), so the new edges have non-negative weight.
For an edge that was already present, \(d'_i+(w(i,j)+h_i-h_j) - d'_j \geq 0\) held before the augmentation, hence \(w(i,j)+(d'_i+h_i)-(d'_j+h_j) \geq 0\): taking \(h_i+d'_i\) as the new potential does not make the weight of \((i,j)\) negative.
So all edge weights are non-negative after the augmentation, and Dijkstra's algorithm correctly finds the shortest paths in the graph.
Reference code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 | |
Practice problems
- Luogu 3381 [Template] Minimum-Cost Maximum Flow
- Luogu 4452 Flight Scheduling
- [SDOI 2009] Morning Run
- [SCOI 2007] Car Repair
- [HAOI 2010] Ordering Stock
- [NOI 2012] Food Festival
References and notes
-
With a heap it runs in \(O(m \log n)\) time on sparse graphs; without one, it runs in \(O(n^2)\) time on dense graphs. ↩
-
For the detailed construction, see min_25's blog. ↩
This page is an unofficial English translation of the original OI Wiki page (revision 5a3c3d0d), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: Ir1d, ouuan, 24OI-bot, sshwy, Henry-ZHR, StudyingFather, TianyiQ, Enter-tainer, blackwhitetony, ksyx, billchenchina, Tiphereth-A, Tiagim (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.