Рассмотрим ориентированный граф \(G = (V, E)\) с истоком \(s\) и стоком \(t\), в котором у каждого ребра \((u, v)\) задана целая стоимость \(w_{uv}\) и целая положительная пропускная способность \(c_{uv}\). Требуется найти максимальный поток, стоимость которого минимальна:
\[ \sum_{(u, v) \in E} f_{uv} \to \max \] \[ \sum_{(u, v) \in E} f_{uv} w_{uv} \to \min \]
Заметим, что рёбра отрицательной стоимости по условию возможны. Мы дополнительно предполагаем, что циклов отрицательного веса нет.
Модифицируем сеть, добавив стандартным образом обратные рёбра, позволяющие «отменять» операции: для каждого ребра \((u, v)\) добавим \((v, u)\), для которого \(c_{vu} = 0\) и \(w_{vu} = -w_{uv}\). Напомним, что остаточной сетью называется граф из рёбер, остаточная пропускная способность которых ненулевая (\(c_{uv}-f_{uv} > 0\)).
Если в остаточной сети нет циклов отрицательного веса, то поток оптимален (и наоборот).
Доказательство:
\(\rightarrow\) Рассмотрим произвольный неоптимальный поток \(f\) и оптимальный поток \(f^*\). Рассмотрим разность \(f^*-f\). Она является циркуляцией, а любая циркуляция может быть разложена на сумму простых циклов. Хотя бы один из этих циклов будет иметь отрицательную стоимость, так как стоимость \(f^*\) меньше стоимости \(f\), что противоречит предположению.
\(\leftarrow\) Пусть цикл существует, тогда мы можем пропустить поток по этому циклу и получить поток меньшей стоимости.
Этот критерий сразу даёт нам относительно простой алгоритм: найдем какой-нибудь максимальный поток и будем «отменять» циклы отрицательного веса в остаточной цепи, пока такие циклы существуют. Искать цикл нам придётся не более \(mUC\) раз где \(U\) — величина потока, \(C\) — максимальная пропускная способность ребра. Этой величиной ограничен модуль минимальной стоимости ответа, а каждый отмененный цикл уменьшает ответ хотя бы на единицу.
Если искать цикл алгоритмом Форда-Беллмана, то асимптотика алгоритма составит \(O(m^2nUC)\) (предполагая, что какой-нибудь максимальный поток мы уже нашли).
Вспомним общий алгоритм поиска максимального потока, основанный на теореме Форда-Фалкерсона: найти какой-нибудь дополняющий путь, пропустить по нему поток и модифицировать сеть, снова найти дополняющий путь и так далее, пока путь из истока в сток существует. Что будет, если мы каждый раз будем искать не произвольный путь, а путь минимальной стоимости? Утверждается, что такой алгоритм найдет максимальный поток минимальной стоимости.
Утверждение. Алгоритм не создает в остаточной сети циклов отрицательного веса.
Изначально в остаточной сети нет циклов отрицательного веса. Мы нашли минимальный путь из \(s\) в \(t\) и модифицировали сеть, возможно добавив какие-то обратные рёбра. Могли ли из-за этих рёбер появиться циклы отрицательного веса? Пусть какое-нибудь обратное ребро \((v, u)\) находится в цикле отрицательного веса. Тогда есть путь Из \(u\) в \(v\) стоимости меньше, чем \(w_{uv}\). Но такое не могло произойти: если бы такой путь существовал, то на этапе поиска дополняющего пути мы выбрали бы его вместо ребра \((u, v)\).
Для поиска дополняющего пути можно использовать алгоритм Форда-Беллмана. Асимптотика в данном случае составит \(O(nmU)\) — искать каждый дополняющий путь мы будем не более \(U\) раз.
Почему мы не использовали алгоритм Дейкстры? Проблема в рёбрах отрицательного веса. Даже если в исходном графе их нет, они могут в процессе алгоритма появиться как обратные. Покажем, как изменить веса рёбер так, чтобы они стали неотрицательными, но информация о кратчайших путях не утратилась: это можно сделать, если дать каждой вершине так называемый «потенциал», который будет учитываться при пересчете стоимостей ребер.
Потенциалом вершины \(v\) будем называть расстояние \(d_v\) от вершины \(s\). Рассмотрим граф из всех достижимых вершин и тех же рёбер, только с изменёнными весами:
\[ w_{uv}' = w_{uv} + d_u - d_v \]
Утверждение 1. Веса всех рёбер графа неотрицательные.
Доказательство. Пусть вес какого-то ребра \((u, v)\) отрицателен, то есть \(w_{uv}' = w_{uv} + d_u - d_v < 0\). Тогда \(d_u + w_{uv} < d_v\), и нарушилось неравенство треугольника: почему мы тогда не использовали ребро \((u, v)\), когда искали кратчайший путь до \(v\)?
Аналогично можно показать, что рёбра на кратчайших путях из \(s\) имеют нулевую стоимость. Заметим, что стоимость обратных рёбер на кратчайших путях тоже будет нулевой: \[ w_{vu}' = w_{vu} + d_v - d_u = -w_{uv} - d_u + d_v = -(w_{uv}) = 0 \]
Утверждение 2. Кратчайшие пути между любыми вершинами остались кратчайшими.
Доказательство. Распишем новую стоимость пути из \(a\) в \(z\).
\[ \begin{aligned} w_{ab}' + \ldots + w_{yz}' &= (w_{ab} + \ldots + w_{yz}) + (d_a + \ldots + d_y) - (d_b + \ldots + d_z) \\&= (w_{ab} + \ldots + w_{yz}) + d_a - d_z \end{aligned} \]
Получаем, что стоимость всех путей из \(a\) в \(z\) лишь изменилась на константу.
Более того, если мы добавим или удалим некоторые рёбра из графа, потенциалы тоже никак не повлияют на кратчайшие пути.
Заметьте, что в доказательстве мы не использовали то, что \(d_v\) — кратчайшие расстояния. Это вообще могут быть произвольные числа.
Утверждение 3. Когда мы проталкиваем поток вдоль кратчайшего пути, удаляя ребра и возможно добавляя обратные, веса в изменённом графе тоже остались корректными (все рёбра неотрицательного веса и все кратчайшие пути остались кратчайшими).
Доказательство. Все добавленные обратные рёбра на кратчайшем пути будут иметь нулевую стомость (утверждение 1), а добавления или удаления рёбер на кратчайшие пути не повлияли (утверждение 2).
Ниже приведено решение задачи о назначениях (паросочетание минимального веса). Для нахождения дополняющего пути используется алгоритм Дейкстры для плотных графов (без приоритетной очереди — каждую итерацию ищется минимум за \(O(n)\)).
cost, cap — параметры сетиpot — потенциалыpar — предок вершины в алгоритме Дейкстры (нужен для проталкивания потока)d — временный массив для алгоритма Дейкстры, куда будут записаны новые расстоянияconst int maxn = 305, inf = 1e9;
int n;
int cost[maxn][maxn], cap[maxn][maxn];
int d[maxn], pot[maxn], par[maxn];
bool dijkstra (int s, int t) {
used[maxn] = {0};
fill(d, d+n, inf);
d[s] = 0;
while (1) {
int v = -1;
for (int u = 0; u < n; u++)
if (!used[u] && (v == -1 && d[u] < d[v]))
v = u;
if (v == -1 || d[v] == inf)
break;
used[v] = 1;
for (int u = 0; u < n; u++) {
int w = cost[v][u] + pot[v] - pot[u];
if (cap[v][u] && d[u] > d[v] + w) {
d[u] = d[v] + w;
par[u] = v;
}
}
}
return d[t] < inf;
}
int mincost_maxflow (int s, int t) {
int ans = 0;
while (dijkstra(s, t)) {
memcpy(pot, d, sizeof(d));
int delta = inf;
for (int v = t; v != s; v = par[v])
delta = min(delta, cap[par[v]][v]);
for (int v = t; v != s; v = par[v]) {
cap[par[v]][v] -= delta;
cap[v][par[v]] += delta;
ans += cost[par[v]][v]*delta;
}
}
return ans;
}В общем случае, алгоритм работает за \(O(U m \log n)\) или \(O(U n^2)\) в случае плотных графов.
В наиболее популярных задачах рёбра обычно с единичной пропускной способностью, и \(U \leq n\) или \(U \leq m\). Например, в задаче о назначениях \(U = n\), и алгоритм работает за \(O(n^3)\), что совпадает с асимптотикой венгерского алгоритма.