Skip to content

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
struct qxx {
  int nex, t, v, c;
};

qxx e[M];
int h[N], cnt = 1;

void add_path(int f, int t, int v, int c) {
  e[++cnt] = qxx{h[f], t, v, c}, h[f] = cnt;
}

void add_flow(int f, int t, int v, int c) {
  add_path(f, t, v, c);
  add_path(t, f, 0, -c);
}

int dis[N], pre[N], incf[N];
bool vis[N];

bool spfa() {
  memset(dis, 0x3f, sizeof(dis));
  queue<int> q;
  q.push(s), dis[s] = 0, incf[s] = INF, incf[t] = 0;
  while (q.size()) {
    int u = q.front();
    q.pop();
    vis[u] = false;
    for (int i = h[u]; i; i = e[i].nex) {
      const int &v = e[i].t, &w = e[i].v, &c = e[i].c;
      if (!w || dis[v] <= dis[u] + c) continue;
      dis[v] = dis[u] + c, incf[v] = min(w, incf[u]), pre[v] = i;
      if (!vis[v]) q.push(v), vis[v] = true;
    }
  }
  return incf[t];
}

int maxflow, mincost;

void update() {
  maxflow += incf[t];
  for (int u = t; u != s; u = e[pre[u] ^ 1].t) {
    e[pre[u]].v -= incf[t], e[pre[u] ^ 1].v += incf[t];
    mincost += incf[t] * e[pre[u]].c;
  }
}

// Usage: while(spfa())update();
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
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>

constexpr int N = 5e3 + 5, M = 1e5 + 5;
constexpr int INF = 0x3f3f3f3f;
int n, m, tot = 1, lnk[N], cur[N], ter[M], nxt[M], cap[M], cost[M], dis[N], ret;
bool vis[N];

void add(int u, int v, int w, int c) {
  ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, cap[tot] = w, cost[tot] = c;
}

void addedge(int u, int v, int w, int c) { add(u, v, w, c), add(v, u, 0, -c); }

bool spfa(int s, int t) {
  memset(dis, 0x3f, sizeof(dis));
  memcpy(cur, lnk, sizeof(lnk));
  std::queue<int> q;
  q.push(s), dis[s] = 0, vis[s] = true;
  while (!q.empty()) {
    int u = q.front();
    q.pop(), vis[u] = false;
    for (int i = lnk[u]; i; i = nxt[i]) {
      int v = ter[i];
      if (cap[i] && dis[v] > dis[u] + cost[i]) {
        dis[v] = dis[u] + cost[i];
        if (!vis[v]) q.push(v), vis[v] = true;
      }
    }
  }
  return dis[t] != INF;
}

int dfs(int u, int t, int flow) {
  if (u == t) return flow;
  vis[u] = true;
  int ans = 0;
  for (int &i = cur[u]; i && ans < flow; i = nxt[i]) {
    int v = ter[i];
    if (!vis[v] && cap[i] && dis[v] == dis[u] + cost[i]) {
      int x = dfs(v, t, std::min(cap[i], flow - ans));
      if (x) ret += x * cost[i], cap[i] -= x, cap[i ^ 1] += x, ans += x;
    }
  }
  vis[u] = false;
  return ans;
}

int mcmf(int s, int t) {
  int ans = 0;
  while (spfa(s, t)) {
    int x;
    while ((x = dfs(s, t, INF))) ans += x;
  }
  return ans;
}

int main() {
  int s, t;
  scanf("%d%d%d%d", &n, &m, &s, &t);
  while (m--) {
    int u, v, w, c;
    scanf("%d%d%d%d", &u, &v, &w, &c);
    addedge(u, v, w, c);
  }
  int ans = mcmf(s, t);
  printf("%d %d\n", ans, ret);
  return 0;
}

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
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
constexpr int INF = 0x3f3f3f3f;
using namespace std;

struct edge {
  int v, f, c, next;
} e[100005];

struct node {
  int v, e;
} p[10005];

struct mypair {
  int dis, id;

  bool operator<(const mypair& a) const { return dis > a.dis; }

  mypair(int d, int x) { dis = d, id = x; }
};

int head[5005], dis[5005], vis[5005], h[5005];
int n, m, s, t, cnt = 1, maxf, minc;

void addedge(int u, int v, int f, int c) {
  e[++cnt].v = v;
  e[cnt].f = f;
  e[cnt].c = c;
  e[cnt].next = head[u];
  head[u] = cnt;
}

bool dijkstra() {
  priority_queue<mypair> q;
  for (int i = 1; i <= n; i++) dis[i] = INF;
  memset(vis, 0, sizeof(vis));
  dis[s] = 0;
  q.push(mypair(0, s));
  while (!q.empty()) {
    int u = q.top().id;
    q.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (int i = head[u]; i; i = e[i].next) {
      int v = e[i].v, nc = e[i].c + h[u] - h[v];
      if (e[i].f && dis[v] > dis[u] + nc) {
        dis[v] = dis[u] + nc;
        p[v].v = u;
        p[v].e = i;
        if (!vis[v]) q.push(mypair(dis[v], v));
      }
    }
  }
  return dis[t] != INF;
}

void spfa() {
  queue<int> q;
  memset(h, 63, sizeof(h));
  h[s] = 0, vis[s] = 1;
  q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    vis[u] = 0;
    for (int i = head[u]; i; i = e[i].next) {
      int v = e[i].v;
      if (e[i].f && h[v] > h[u] + e[i].c) {
        h[v] = h[u] + e[i].c;
        if (!vis[v]) {
          vis[v] = 1;
          q.push(v);
        }
      }
    }
  }
}

int main() {
  scanf("%d%d%d%d", &n, &m, &s, &t);
  for (int i = 1; i <= m; i++) {
    int u, v, f, c;
    scanf("%d%d%d%d", &u, &v, &f, &c);
    addedge(u, v, f, c);
    addedge(v, u, 0, -c);
  }
  spfa();  // compute the initial potentials first
  while (dijkstra()) {
    int minf = INF;
    for (int i = 1; i <= n; i++) h[i] += dis[i];
    for (int i = t; i != s; i = p[i].v) minf = min(minf, e[p[i].e].f);
    for (int i = t; i != s; i = p[i].v) {
      e[p[i].e].f -= minf;
      e[p[i].e ^ 1].f += minf;
    }
    maxf += minf;
    minc += minf * h[t];
  }
  printf("%d %d\n", maxf, minc);
  return 0;
}

Practice problems

References and notes


  1. 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. ↩

  2. For the detailed construction, see min_25's blog. ↩