Поток минимальной стоимости (min-cost max-flow): SPFA, потенциалы и Дейкстра

Поток минимальной стоимости простыми словами: остаточная сеть со стоимостями, кратчайшие пути через SPFA, потенциалы Джонсона с Дейкстрой и задача о назначениях. Код на Python.

12 мин чтенияалгоритмы · графы · python

Коротко

ВариантПоиск путиСложностьКогда брать
Последовательные кратчайшие путиSPFA / Беллман–ФордO(F⋅V⋅E)O(F \cdot V \cdot E)быстро написать, есть отрицательные стоимости
То же с потенциалами ДжонсонаДейкстра на кучеO(F⋅Elog⁡V)O(F \cdot E \log V)основной рабочий вариант
Задача о назначениях n×nn \times nлюбой из двухnn итераций по одному путикогда граф разреженный или есть ёмкости больше 1
  • Задача: пропустить из истока в сток максимальный поток (или ровно kk единиц) так, чтобы суммарная стоимость была минимальной.
  • Идея: раз за разом пускать поток по самому дешёвому пути в остаточной сети. Обратные рёбра получают стоимость с минусом.
  • Отрицательные рёбра в остаточной сети появляются всегда, поэтому обычная Дейкстра не годится — либо SPFA, либо потенциалы.
  • FF — величина потока: алгоритм псевдополиномиальный, число итераций зависит от ответа.

Задача

Обычный максимальный поток отвечает на вопрос «сколько можно прокачать». Но на практике у каждого канала есть ещё и цена: доставка по одной дороге стоит дороже, чем по другой, один исполнитель берёт за задачу больше другого.

Формально: дан ориентированный граф, у каждого ребра (u,v)(u, v) есть пропускная способность c(u,v)c(u, v) и стоимость w(u,v)w(u, v) за единицу потока. Стоимость потока:

cost(f)=∑(u,v)f(u,v)⋅w(u,v)\text{cost}(f) = \sum_{(u,v)} f(u, v) \cdot w(u, v)

Нужно найти поток максимальной величины, а среди всех таких — самый дешёвый. Частый вариант: найти самый дешёвый поток ровно величины kk (если он существует).

Пример, на котором будем разбираться:

          4, 1          2, 6
     S ---------→ A ---------→ T
     |            |            ↑
 2,5 |       2, 1 |            | 4, 1
     ↓            ↓            |
     B ←----------+            |
     |                         |
     +-------------------------+

Подпись 4, 1 означает «пропускная способность 4, стоимость 1». Рёбра: S→A (4, 1), S→B (2, 5), A→B (2, 1), A→T (2, 6), B→T (4, 1). Максимальный поток здесь 6, и вопрос — как распределить его дешевле всего.

Почему не хватает обычного максимального потока

Эдмондс–Карп ищет дополняющий путь через BFS — кратчайший по числу рёбер, а не по деньгам. Он найдёт поток величины 6, но какой именно — зависит от порядка обхода. Можно, например, получить S→A→T и S→B→T по 2 единицы, а затем S→A→B→T ещё 2. Стоимость в этом случае совпадёт с оптимальной случайно; на чуть другой сети — уже нет.

Жадность «бери самые дешёвые рёбра» тоже не работает: дешёвое ребро может оказаться единственным выходом для другого маршрута, и занять его первым — ошибка. Нужен механизм отката, и в потоках он уже есть — обратные рёбра.

Остаточная сеть со стоимостями

Как и в обычном потоке, для каждого ребра u → v храним парное обратное v → u с нулевой пропускной способностью. Новое правило одно:

Обратное ребро имеет стоимость −w(u,v)-w(u, v).

Логика простая. Пустить единицу по обратному ребру — значит отменить единицу, которая шла по прямому. Мы перестаём за неё платить, то есть получаем ww назад. Отсюда минус.

было:    u --(cap 3, cost 4)--→ v      обратное: v --(cap 0, cost -4)--→ u
пустили 2 единицы
стало:   u --(cap 1, cost 4)--→ v      обратное: v --(cap 2, cost -4)--→ u

Следствие: даже если все исходные стоимости неотрицательны, в остаточной сети отрицательные рёбра появятся после первой же итерации. Это главный технический момент всей темы.

Алгоритм последовательных кратчайших путей

Алгоритм почти дословно повторяет Форда–Фалкерсона, только путь выбирается по стоимости:

  1. Найти кратчайший по стоимости путь из S в T в остаточной сети (по рёбрам с ненулевым остатком).
  2. Если пути нет — стоп, поток максимален.
  3. Найти узкое место пути δ\delta — минимальный остаток на рёбрах.
  4. Пустить δ\delta единиц, уменьшить остатки прямых рёбер и увеличить остатки обратных. Стоимость растёт на δ⋅dist(T)\delta \cdot \text{dist}(T).
  5. Вернуться к шагу 1.

Почему это даёт оптимум

Ключевой факт: поток величины kk имеет минимальную стоимость тогда и только тогда, когда в его остаточной сети нет циклов отрицательной стоимости. Если такой цикл есть, по нему можно пустить единицу и стать дешевле при той же величине потока. Если нет — дешевле не бывает.

Алгоритм поддерживает этот инвариант. В начале поток нулевой и отрицательных циклов нет (если их не было в исходном графе). Каждый раз мы идём по кратчайшему пути, а после проталкивания вдоль него не возникает отрицательных циклов — новые обратные рёбра лежат на кратчайшем пути и «замыкаются» с нулевой приведённой длиной. Значит, после каждой итерации текущий поток — самый дешёвый среди потоков своей величины.

Отсюда полезный побочный эффект: если остановиться на величине kk, получим минимальную стоимость потока ровно kk. А стоимость пути на каждой итерации не убывает — функция «стоимость от величины потока» выпуклая.

Разбор на примере

ИтерацияКратчайший путьСтоимость путиδ\deltaПотокСтоимость
1S → A → B → T1 + 1 + 1 = 3226
2S → B → T5 + 1 = 62418
3S → A → T1 + 6 = 72632

После третьей итерации B→T и A→T насыщены, путей нет. Ответ: поток 6, стоимость 32. Видно, что цена пути растёт: 3, 6, 7 — та самая выпуклость.

Реализация с SPFA

Для поиска пути в графе с отрицательными рёбрами подходит Беллман–Форд. На практике пишут его очередную версию — SPFA (Shortest Path Faster Algorithm): в очередь кладётся вершина, расстояние до которой только что улучшилось, и релаксируются только её рёбра. В худшем случае это те же O(V⋅E)O(V \cdot E), но обычно гораздо быстрее.

from collections import deque import heapq INF = float('inf') class MinCostFlow: def __init__(self, n): self.n = n # ребро: [куда, остаток, стоимость, индекс обратного ребра] self.graph = [[] for _ in range(n)] def add_edge(self, u, v, cap, cost): self.graph[u].append([v, cap, cost, len(self.graph[v])]) self.graph[v].append([u, 0, -cost, len(self.graph[u]) - 1]) def _spfa(self, s): dist = [INF] * self.n prev = [None] * self.n # (вершина, номер ребра в её списке) in_queue = [False] * self.n dist[s] = 0 queue = deque([s]) while queue: u = queue.popleft() in_queue[u] = False for i, (v, cap, cost, _) in enumerate(self.graph[u]): if cap > 0 and dist[u] + cost < dist[v]: dist[v] = dist[u] + cost prev[v] = (u, i) if not in_queue[v]: in_queue[v] = True queue.append(v) return dist, prev def _push(self, s, t, prev, limit): # узкое место пути f, v = limit, t while v != s: u, i = prev[v] f = min(f, self.graph[u][i][1]) v = u # проталкиваем f единиц v = t while v != s: u, i = prev[v] edge = self.graph[u][i] edge[1] -= f self.graph[v][edge[3]][1] += f v = u return f def flow_spfa(self, s, t, max_flow=INF): flow = cost = 0 while flow < max_flow: dist, prev = self._spfa(s) if dist[t] == INF: break f = self._push(s, t, prev, max_flow - flow) flow += f cost += f * dist[t] return flow, cost g = MinCostFlow(4) S, A, B, T = 0, 1, 2, 3 g.add_edge(S, A, 4, 1) g.add_edge(S, B, 2, 5) g.add_edge(A, B, 2, 1) g.add_edge(A, T, 2, 6) g.add_edge(B, T, 4, 1) print(g.flow_spfa(S, T)) # (6, 32)

Несколько деталей реализации:

  • Рёбра хранятся списками [куда, остаток, стоимость, индекс обратного]. Индекс обратного ребра позволяет за O(1)O(1) обновить пару — это стандартный приём из максимального потока.
  • Параметр max_flow превращает алгоритм в «самый дешёвый поток ровно kk»: вызов flow_spfa(S, T, 3) на примере вернёт (3, 12).
  • Сложность: каждая итерация увеличивает поток хотя бы на 1, итераций не больше FF, каждая стоит O(V⋅E)O(V \cdot E) в худшем случае.

Потенциалы Джонсона и Дейкстра

Дейкстра с кучей работает за O(Elog⁡V)O(E \log V) и, в отличие от SPFA, предсказуем. Мешают ей только отрицательные рёбра. Тот же трюк, что в алгоритме Джонсона, снимает проблему.

Приведённые стоимости

Заведём для каждой вершины потенциал h(v)h(v) и будем искать пути по приведённым стоимостям:

wh(u,v)=w(u,v)+h(u)−h(v)w_h(u, v) = w(u, v) + h(u) - h(v)

Для любого пути из ss в tt промежуточные потенциалы сокращаются (телескопическая сумма), поэтому

lenh(P)=len(P)+h(s)−h(t).\text{len}_h(P) = \text{len}(P) + h(s) - h(t).

Все пути из ss в tt сдвигаются на одну и ту же константу, значит, кратчайший путь остаётся кратчайшим. А если взять h(v)=dist(s,v)h(v) = \text{dist}(s, v), то по неравенству треугольника dist(v)≤dist(u)+w(u,v)\text{dist}(v) \le \text{dist}(u) + w(u, v) все приведённые стоимости станут неотрицательными.

Почему потенциалы не ломаются после проталкивания

После очередной Дейкстры обновляем h(v)+=d(v)h(v) \mathrel{+}= d(v), где d(v)d(v) — найденное приведённое расстояние. Новые потенциалы равны настоящим кратчайшим расстояниям в текущей сети, и для всех старых рёбер приведённая стоимость неотрицательна.

Остаётся проверить рёбра, которые появились после проталкивания. Новое обратное ребро v→uv \to u возникает только на рёбрах кратчайшего пути, где h(v)=h(u)+w(u,v)h(v) = h(u) + w(u, v). Его приведённая стоимость:

−w(u,v)+h(v)−h(u)=0.-w(u, v) + h(v) - h(u) = 0.

Ноль — значит, всё в порядке, Дейкстра снова применима. Это и есть причина, по которой алгоритм с потенциалами корректен.

Стартовые потенциалы

Если исходные стоимости неотрицательны, можно начать с h≡0h \equiv 0. Если отрицательные есть (но нет отрицательных циклов), один раз запускаем SPFA и берём расстояния как стартовые потенциалы. Вершины, недостижимые из истока, никогда не станут достижимыми, поэтому им можно поставить 0.

# метод класса MinCostFlow def flow_dijkstra(self, s, t, max_flow=INF): n = self.n # стартовые потенциалы: если есть отрицательные стоимости, один раз SPFA h, _ = self._spfa(s) h = [x if x < INF else 0 for x in h] flow = cost = 0 while flow < max_flow: dist = [INF] * n prev = [None] * n dist[s] = 0 heap = [(0, s)] while heap: d, u = heapq.heappop(heap) if d > dist[u]: continue for i, (v, cap, c, _) in enumerate(self.graph[u]): nd = d + c + h[u] - h[v] # приведённая стоимость >= 0 if cap > 0 and nd < dist[v]: dist[v] = nd prev[v] = (u, i) heapq.heappush(heap, (nd, v)) if dist[t] == INF: break for v in range(n): if dist[v] < INF: h[v] += dist[v] f = self._push(s, t, prev, max_flow - flow) flow += f cost += f * (h[t] - h[s]) return flow, cost

Настоящая стоимость пути — h[t] - h[s] после обновления: потенциалы и есть настоящие расстояния. На примере метод возвращает те же (6, 32).

Я сверил обе версии между собой на двух тысячах случайных графов (в том числе с отрицательными стоимостями на DAG и с ограничением max_flow) и с networkx.max_flow_min_cost — ответы совпали.

SPFA или Дейкстра

Асимптотически Дейкстра выигрывает: O(Elog⁡V)O(E \log V) против O(V⋅E)O(V \cdot E) на итерацию. На практике всё зависит от графа. На плотной задаче о назначениях 150×150150 \times 150 в Python обе версии отработали примерно за 2 секунды — SPFA на таких графах сходится быстро. Зато SPFA можно «завалить» специально подобранным тестом, и на олимпиадах это делают. Если пишете для продакшена или контеста с сильными тестами — берите потенциалы.

Задача о назначениях

Классическое применение. Есть nn работников и nn задач, cost[i][j] — цена, если ii-й работник делает jj-ю задачу. Каждому нужно дать ровно одну задачу, суммарная цена — минимальна.

Сводится к потоку так:

  • исток → каждый работник: пропускная способность 1, стоимость 0;
  • работник ii → задача jj: пропускная способность 1, стоимость cost[i][j];
  • каждая задача → сток: пропускная способность 1, стоимость 0.

Максимальный поток равен nn, а его минимальная стоимость — ответ. Пара (i,j)(i, j) выбрана, если ребро i→ji \to j насыщено.

def assignment(cost): n = len(cost) s, t = 2 * n, 2 * n + 1 g = MinCostFlow(2 * n + 2) for i in range(n): g.add_edge(s, i, 1, 0) # исток -> работник g.add_edge(n + i, t, 1, 0) # задача -> сток for j in range(n): g.add_edge(i, n + j, 1, cost[i][j]) flow, total = g.flow_dijkstra(s, t) pairs = [] for i in range(n): for v, cap, c, _ in g.graph[i]: if n <= v < 2 * n and cap == 0: # ребро насыщено -> пара выбрана pairs.append((i, v - n)) return total, pairs cost = [ [9, 2, 7, 8], [6, 4, 3, 7], [5, 8, 1, 8], [7, 6, 9, 4], ] print(assignment(cost)) # (13, [(0, 1), (1, 0), (2, 2), (3, 3)])

Ответ сверен с scipy.optimize.linear_sum_assignment на сотнях случайных матриц.

Для полной квадратной матрицы есть специализированный венгерский алгоритм за O(n3)O(n^3) — по сути это тот же min-cost flow с потенциалами, только без явных рёбер. Поток выигрывает в гибкости:

  • Ёмкости больше 1. Работник может взять до трёх задач — ставим cap = 3 на ребро из истока.
  • Разреженный граф. Не каждый умеет делать каждую задачу — просто не добавляем ребро.
  • Максимизация. Нужна максимальная прибыль — берём стоимости со знаком минус (отрицательных циклов при этом не будет: граф ацикличен).
  • Неполное назначение. Нужно выбрать ровно kk пар — max_flow=k.

Без весов та же сеть даёт обычное максимальное паросочетание, которое удобнее искать алгоритмом Куна.

Где ещё встречается

  • Транспортная задача. Склады с запасами, магазины со спросом, цена перевозки за единицу. Исток → склады (ёмкость = запас), склады → магазины (цена перевозки), магазины → сток (ёмкость = спрос).
  • kk непересекающихся путей минимальной длины. Ёмкость каждого ребра 1, стоимость — длина, пускаем поток kk. Если пути не должны делить вершины, каждую вершину раздваиваем на «вход» и «выход» с ребром ёмкости 1.
  • Расписания и распределение ресурсов. Смены, аудитории, серверы под задачи — всё, где есть «кто-то → что-то» с ценой и ограничением на количество.
  • Задачи на отрезки и интервалы, где каждый отрезок можно взять с весом, а точка покрывается не более kk раз, — классика контестов, решается потоком по прямой.

Частые ошибки

  • Забыть минус у обратного ребра. Алгоритм работает, но выдаёт завышенную стоимость: «отмена» потока не возвращает деньги.
  • Обычная Дейкстра без потенциалов. Отрицательные рёбра появляются после первой же итерации, и ответ становится неверным, причём не всегда — такую ошибку трудно поймать на маленьких тестах.
  • Отрицательный цикл в исходном графе. Последовательные кратчайшие пути исходят из того, что его нет. Если цикл есть, нужен другой алгоритм — например, сокращение отрицательных циклов (cycle cancelling).
  • Считать стоимость как dist[t] в версии с потенциалами. dist там приведённое; настоящая цена пути — h[t] - h[s].
  • Переполнение и INF. В C++/Java суммы поток×стоимость\text{поток} \times \text{стоимость} легко выходят за int, берите long long. Константа INF должна быть больше любой реальной длины пути.
  • Ожидать полиномиальности. Число итераций до FF; если ёмкости порядка 10910^9, а пути проталкивают по единице, алгоритм не успеет. Обычно спасает то, что δ\delta — узкое место, а не 1, но гарантий нет.

На собеседовании

Min-cost flow — тема скорее олимпиадная. На стандартных алгоритмических интервью его почти не просят писать с нуля, но он всплывает в двух ситуациях.

Первая — задача, которая выглядит как жадность или ДП, а на самом деле является назначением или транспортной задачей. Здесь ценится сам факт, что вы узнали модель: «это поток минимальной стоимости, вот сеть, вот ёмкости и стоимости». Дальше можно обсудить сложность и сказать, что в продакшене взяли бы готовый солвер (OR-Tools, networkx, LP).

Вторая — разговор о графах «вглубь»: почему у обратного ребра стоимость отрицательная, зачем потенциалы, почему Дейкстра с ними корректна. Ответ на последний вопрос — одна строка: приведённая стоимость нового обратного ребра на кратчайшем пути равна нулю.

Что запомнить

  • Min-cost max-flow = Форд–Фалкерсон, где дополняющий путь — кратчайший по стоимости.
  • Обратное ребро стоит −w-w: отмена потока возвращает деньги.
  • Корректность держится на инварианте «в остаточной сети нет отрицательных циклов».
  • SPFA — проще, O(V⋅E)O(V \cdot E) на итерацию в худшем случае. Потенциалы Джонсона + Дейкстра — O(Elog⁡V)O(E \log V) на итерацию.
  • Задача о назначениях — частный случай: исток → работники → задачи → сток, все ёмкости 1.
  • Ограничение max_flow = k даёт самый дешёвый поток ровно величины kk.

Потренироваться в спокойной обстановке

Все задачи