Поток минимальной стоимости

Рассмотрим ориентированный граф $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^\ast$. Рассмотрим разность $f^\ast-f$. Она является циркуляцией, а любая циркуляция может быть разложена на сумму простых циклов. Хотя бы один из этих циклов будет иметь отрицательную стоимость, так как стоимость $f^\ast$ меньше стоимости $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).

#Итоговый алгоритм

Модифицируем сеть, добавив обратные рёбра.
Если в исходном графе есть рёбра отрицательного веса (но нет циклов отрицательного веса), то посчитать изначальные потенциалы (расстояния) алгоритмом Форда-Беллмана. Иначе достаточно положить потенциалы изначально равными нулю.
Пока максимальный поток не найден:
1. Посчитать алгоритмом Дейкстры кратчайшие расстояния от $s$, используя для веса формулу с потенциалами, записать их в $d$.
2. Протолкнуть максимально возможный поток вдоль кратчайшего пути $s \leadsto t$ и обновить остаточную сеть.

#Реализация

Ниже приведено решение задачи о назначениях (паросочетание минимального веса). Для нахождения дополняющего пути используется алгоритм Дейкстры для плотных графов (без очереди с приоритетами — каждую итерацию ищется минимум за $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)$, что совпадает с асимптотикой венгерского алгоритма.