Поток минимальной стоимости (min-cost max-flow): SPFA, потенциалы и Дейкстра
Поток минимальной стоимости простыми словами: остаточная сеть со стоимостями, кратчайшие пути через SPFA, потенциалы Джонсона с Дейкстрой и задача о назначениях. Код на Python.
Коротко
| Вариант | Поиск пути | Сложность | Когда брать |
|---|---|---|---|
| Последовательные кратчайшие пути | SPFA / Беллман–Форд | быстро написать, есть отрицательные стоимости | |
| То же с потенциалами Джонсона | Дейкстра на куче | основной рабочий вариант | |
| Задача о назначениях | любой из двух | итераций по одному пути | когда граф разреженный или есть ёмкости больше 1 |
- Задача: пропустить из истока в сток максимальный поток (или ровно единиц) так, чтобы суммарная стоимость была минимальной.
- Идея: раз за разом пускать поток по самому дешёвому пути в остаточной сети. Обратные рёбра получают стоимость с минусом.
- Отрицательные рёбра в остаточной сети появляются всегда, поэтому обычная Дейкстра не годится — либо SPFA, либо потенциалы.
- — величина потока: алгоритм псевдополиномиальный, число итераций зависит от ответа.
Задача
Обычный максимальный поток отвечает на вопрос «сколько можно прокачать». Но на практике у каждого канала есть ещё и цена: доставка по одной дороге стоит дороже, чем по другой, один исполнитель берёт за задачу больше другого.
Формально: дан ориентированный граф, у каждого ребра есть пропускная способность и стоимость за единицу потока. Стоимость потока:
Нужно найти поток максимальной величины, а среди всех таких — самый дешёвый. Частый вариант: найти самый дешёвый поток ровно величины (если он существует).
Пример, на котором будем разбираться:
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 с нулевой пропускной способностью. Новое правило одно:
Обратное ребро имеет стоимость .
Логика простая. Пустить единицу по обратному ребру — значит отменить единицу, которая шла по прямому. Мы перестаём за неё платить, то есть получаем назад. Отсюда минус.
было: 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
Следствие: даже если все исходные стоимости неотрицательны, в остаточной сети отрицательные рёбра появятся после первой же итерации. Это главный технический момент всей темы.
Алгоритм последовательных кратчайших путей
Алгоритм почти дословно повторяет Форда–Фалкерсона, только путь выбирается по стоимости:
- Найти кратчайший по стоимости путь из
SвTв остаточной сети (по рёбрам с ненулевым остатком). - Если пути нет — стоп, поток максимален.
- Найти узкое место пути — минимальный остаток на рёбрах.
- Пустить единиц, уменьшить остатки прямых рёбер и увеличить остатки обратных. Стоимость растёт на .
- Вернуться к шагу 1.
Почему это даёт оптимум
Ключевой факт: поток величины имеет минимальную стоимость тогда и только тогда, когда в его остаточной сети нет циклов отрицательной стоимости. Если такой цикл есть, по нему можно пустить единицу и стать дешевле при той же величине потока. Если нет — дешевле не бывает.
Алгоритм поддерживает этот инвариант. В начале поток нулевой и отрицательных циклов нет (если их не было в исходном графе). Каждый раз мы идём по кратчайшему пути, а после проталкивания вдоль него не возникает отрицательных циклов — новые обратные рёбра лежат на кратчайшем пути и «замыкаются» с нулевой приведённой длиной. Значит, после каждой итерации текущий поток — самый дешёвый среди потоков своей величины.
Отсюда полезный побочный эффект: если остановиться на величине , получим минимальную стоимость потока ровно . А стоимость пути на каждой итерации не убывает — функция «стоимость от величины потока» выпуклая.
Разбор на примере
| Итерация | Кратчайший путь | Стоимость пути | Поток | Стоимость | |
|---|---|---|---|---|---|
| 1 | S → A → B → T | 1 + 1 + 1 = 3 | 2 | 2 | 6 |
| 2 | S → B → T | 5 + 1 = 6 | 2 | 4 | 18 |
| 3 | S → A → T | 1 + 6 = 7 | 2 | 6 | 32 |
После третьей итерации B→T и A→T насыщены, путей нет. Ответ: поток 6, стоимость 32. Видно, что цена пути растёт: 3, 6, 7 — та самая выпуклость.
Реализация с SPFA
Для поиска пути в графе с отрицательными рёбрами подходит Беллман–Форд. На практике пишут его очередную версию — SPFA (Shortest Path Faster Algorithm): в очередь кладётся вершина, расстояние до которой только что улучшилось, и релаксируются только её рёбра. В худшем случае это те же , но обычно гораздо быстрее.
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)
Несколько деталей реализации:
- Рёбра хранятся списками
[куда, остаток, стоимость, индекс обратного]. Индекс обратного ребра позволяет за обновить пару — это стандартный приём из максимального потока. - Параметр
max_flowпревращает алгоритм в «самый дешёвый поток ровно »: вызовflow_spfa(S, T, 3)на примере вернёт(3, 12). - Сложность: каждая итерация увеличивает поток хотя бы на 1, итераций не больше , каждая стоит в худшем случае.
Потенциалы Джонсона и Дейкстра
Дейкстра с кучей работает за и, в отличие от SPFA, предсказуем. Мешают ей только отрицательные рёбра. Тот же трюк, что в алгоритме Джонсона, снимает проблему.
Приведённые стоимости
Заведём для каждой вершины потенциал и будем искать пути по приведённым стоимостям:
Для любого пути из в промежуточные потенциалы сокращаются (телескопическая сумма), поэтому
Все пути из в сдвигаются на одну и ту же константу, значит, кратчайший путь остаётся кратчайшим. А если взять , то по неравенству треугольника все приведённые стоимости станут неотрицательными.
Почему потенциалы не ломаются после проталкивания
После очередной Дейкстры обновляем , где — найденное приведённое расстояние. Новые потенциалы равны настоящим кратчайшим расстояниям в текущей сети, и для всех старых рёбер приведённая стоимость неотрицательна.
Остаётся проверить рёбра, которые появились после проталкивания. Новое обратное ребро возникает только на рёбрах кратчайшего пути, где . Его приведённая стоимость:
Ноль — значит, всё в порядке, Дейкстра снова применима. Это и есть причина, по которой алгоритм с потенциалами корректен.
Стартовые потенциалы
Если исходные стоимости неотрицательны, можно начать с . Если отрицательные есть (но нет отрицательных циклов), один раз запускаем 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 или Дейкстра
Асимптотически Дейкстра выигрывает: против на итерацию. На практике всё зависит от графа. На плотной задаче о назначениях в Python обе версии отработали примерно за 2 секунды — SPFA на таких графах сходится быстро. Зато SPFA можно «завалить» специально подобранным тестом, и на олимпиадах это делают. Если пишете для продакшена или контеста с сильными тестами — берите потенциалы.
Задача о назначениях
Классическое применение. Есть работников и задач, cost[i][j] — цена, если -й работник делает -ю задачу. Каждому нужно дать ровно одну задачу, суммарная цена — минимальна.
Сводится к потоку так:
- исток → каждый работник: пропускная способность 1, стоимость 0;
- работник → задача : пропускная способность 1, стоимость
cost[i][j]; - каждая задача → сток: пропускная способность 1, стоимость 0.
Максимальный поток равен , а его минимальная стоимость — ответ. Пара выбрана, если ребро насыщено.
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 на сотнях случайных матриц.
Для полной квадратной матрицы есть специализированный венгерский алгоритм за — по сути это тот же min-cost flow с потенциалами, только без явных рёбер. Поток выигрывает в гибкости:
- Ёмкости больше 1. Работник может взять до трёх задач — ставим
cap = 3на ребро из истока. - Разреженный граф. Не каждый умеет делать каждую задачу — просто не добавляем ребро.
- Максимизация. Нужна максимальная прибыль — берём стоимости со знаком минус (отрицательных циклов при этом не будет: граф ацикличен).
- Неполное назначение. Нужно выбрать ровно пар —
max_flow=k.
Без весов та же сеть даёт обычное максимальное паросочетание, которое удобнее искать алгоритмом Куна.
Где ещё встречается
- Транспортная задача. Склады с запасами, магазины со спросом, цена перевозки за единицу. Исток → склады (ёмкость = запас), склады → магазины (цена перевозки), магазины → сток (ёмкость = спрос).
- непересекающихся путей минимальной длины. Ёмкость каждого ребра 1, стоимость — длина, пускаем поток . Если пути не должны делить вершины, каждую вершину раздваиваем на «вход» и «выход» с ребром ёмкости 1.
- Расписания и распределение ресурсов. Смены, аудитории, серверы под задачи — всё, где есть «кто-то → что-то» с ценой и ограничением на количество.
- Задачи на отрезки и интервалы, где каждый отрезок можно взять с весом, а точка покрывается не более раз, — классика контестов, решается потоком по прямой.
Частые ошибки
- Забыть минус у обратного ребра. Алгоритм работает, но выдаёт завышенную стоимость: «отмена» потока не возвращает деньги.
- Обычная Дейкстра без потенциалов. Отрицательные рёбра появляются после первой же итерации, и ответ становится неверным, причём не всегда — такую ошибку трудно поймать на маленьких тестах.
- Отрицательный цикл в исходном графе. Последовательные кратчайшие пути исходят из того, что его нет. Если цикл есть, нужен другой алгоритм — например, сокращение отрицательных циклов (cycle cancelling).
- Считать стоимость как
dist[t]в версии с потенциалами.distтам приведённое; настоящая цена пути —h[t] - h[s]. - Переполнение и
INF. В C++/Java суммы легко выходят заint, беритеlong long. КонстантаINFдолжна быть больше любой реальной длины пути. - Ожидать полиномиальности. Число итераций до ; если ёмкости порядка , а пути проталкивают по единице, алгоритм не успеет. Обычно спасает то, что — узкое место, а не 1, но гарантий нет.
На собеседовании
Min-cost flow — тема скорее олимпиадная. На стандартных алгоритмических интервью его почти не просят писать с нуля, но он всплывает в двух ситуациях.
Первая — задача, которая выглядит как жадность или ДП, а на самом деле является назначением или транспортной задачей. Здесь ценится сам факт, что вы узнали модель: «это поток минимальной стоимости, вот сеть, вот ёмкости и стоимости». Дальше можно обсудить сложность и сказать, что в продакшене взяли бы готовый солвер (OR-Tools, networkx, LP).
Вторая — разговор о графах «вглубь»: почему у обратного ребра стоимость отрицательная, зачем потенциалы, почему Дейкстра с ними корректна. Ответ на последний вопрос — одна строка: приведённая стоимость нового обратного ребра на кратчайшем пути равна нулю.
Что запомнить
- Min-cost max-flow = Форд–Фалкерсон, где дополняющий путь — кратчайший по стоимости.
- Обратное ребро стоит : отмена потока возвращает деньги.
- Корректность держится на инварианте «в остаточной сети нет отрицательных циклов».
- SPFA — проще, на итерацию в худшем случае. Потенциалы Джонсона + Дейкстра — на итерацию.
- Задача о назначениях — частный случай: исток → работники → задачи → сток, все ёмкости 1.
- Ограничение
max_flow = kдаёт самый дешёвый поток ровно величины .