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

Рассмотрим ориентированный граф $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$).

Критерий оптимальности

Если в остаточной сети нет циклов отрицательного веса, то поток оптимален (и наоборот).

Доказательство:

$\to$ Рассмотрим произвольный неоптимальный поток $f$ и оптимальный поток $f^{\ast }$. Рассмотрим разность $f^{\ast }-f$. Она является циркуляцией, а любая циркуляция может быть разложена на сумму простых циклов. Хотя бы один из этих циклов будет иметь отрицательную стоимость, так как стоимость $f^{\ast }$ меньше стоимости $f$, что противоречит предположению.

$\leftarrow$ Пусть цикл существует, тогда мы можем пропустить поток по этому циклу и получить поток меньшей стоимости.

Отмена циклов

Этот критерий сразу даёт нам относительно простой алгоритм: найдем какой-нибудь максимальный поток и будем «отменять» циклы отрицательного веса в остаточной цепи, пока такие циклы существуют. Искать цикл нам придётся не более $mUC$ раз где $U$ — величина потока, $C$ — максимальная пропускная способность ребра. Этой величиной ограничен модуль минимальной стоимости ответа, а каждый отмененный цикл уменьшает ответ хотя бы на единицу.

Если искать цикл алгоритмом Форда-Беллмана, то асимптотика алгоритма составит $O(m^{2}nUC)$ (предполагая, что какой-нибудь максимальный поток мы уже нашли).

Дополняющие пути

Вспомним общий алгоритм поиска максимального потока, основанный на теореме Форда-Фалкерсона: найти какой-нибудь дополняющий путь, пропустить по нему поток и модифицировать сеть, снова найти дополняющий путь и так далее, пока путь из истока в сток существует. Что будет, если мы каждый раз будем искать не произвольный путь, а путь минимальной стоимости? Утверждается, что такой алгоритм найдет максимальный поток минимальной стоимости.

Утверждение. Алгоритм не создает в остаточной сети циклов отрицательного веса.

Изначально в остаточной сети нет циклов отрицательного веса. Мы нашли минимальный путь из $s$ в $t$ и модифицировали сеть, возможно добавив какие-то обратные рёбра. Могли ли из-за этих рёбер появиться циклы отрицательного веса? Пусть какое-нибудь обратное ребро $(v,u)$ находится в цикле отрицательного веса. Тогда есть путь Из $u$ в $v$ стоимости меньше, чем $w_{uv}$. Но такое не могло произойти: если бы такой путь существовал, то на этапе поиска дополняющего пути мы выбрали бы его вместо ребра $(u,v)$.

Для поиска дополняющего пути можно использовать алгоритм Форда-Беллмана. Асимптотика в данном случае составит $O(nmU)$ — искать каждый дополняющий путь мы будем не более $U$ раз.

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

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

Потенциалом вершины $v$ будем называть расстояние $d_v$ от вершины $s$. Рассмотрим граф из всех достижимых вершин и тех же рёбер, только с изменёнными весами:

$$w_{uv}^{\prime }=w_{uv}+d_u-d_v$$

Утверждение 1. Веса всех рёбер графа неотрицательные.

Доказательство. Пусть вес какого-то ребра $(u,v)$ отрицателен, то есть $w_{uv}^{\prime }=w_{uv}+d_u-d_v<0$. Тогда $d_u+w_{uv}<d_v$, и нарушилось неравенство треугольника: почему мы тогда не использовали ребро $(u,v)$, когда искали кратчайший путь до $v$?

Аналогично можно показать, что рёбра на кратчайших путях из $s$ имеют нулевую стоимость. Заметим, что стоимость обратных рёбер на кратчайших путях тоже будет нулевой: $$w_{vu}^{\prime }=w_{vu}+d_v-d_u=-w_{uv}-d_u+d_v=-(w_{uv})=0$$

Утверждение 2. Кратчайшие пути между любыми вершинами остались кратчайшими.

Доказательство. Распишем новую стоимость пути из $a$ в $z$.

$$\begin{array}{rl}{w}_{ab}^{\prime }+\dots +w_{yz}^{\prime }& =(w_{ab}+\dots +w_{yz})+(d_a+\dots +d_y)-(d_b+\dots +d_z)\\ & =(w_{ab}+\dots +w_{yz})+d_a-d_z\end{array}$$

Получаем, что стоимость всех путей из $a$ в $z$ лишь изменилась на константу.

Более того, если мы добавим или удалим некоторые рёбра из графа, потенциалы тоже никак не повлияют на кратчайшие пути.

Заметьте, что в доказательстве мы не использовали то, что $d_v$ — кратчайшие расстояния. Это вообще могут быть произвольные числа.

Утверждение 3. Когда мы проталкиваем поток вдоль кратчайшего пути, удаляя ребра и возможно добавляя обратные, веса в изменённом графе тоже остались корректными (все рёбра неотрицательного веса и все кратчайшие пути остались кратчайшими).

Доказательство. Все добавленные обратные рёбра на кратчайшем пути будут иметь нулевую стомость (утверждение 1), а добавления или удаления рёбер на кратчайшие пути не повлияли (утверждение 2).

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

• Модифицируем сеть, добавив обратные рёбра.
• Если в исходном графе есть рёбра отрицательного веса (но нет циклов отрицательного веса), то посчитать изначальные потенциалы (расстояния) алгоритмом Форда-Беллмана. Иначе достаточно положить потенциалы изначально равными нулю.
• Пока максимальный поток не найден:
• • Посчитать алгоритмом Дейкстры кратчайшие расстояния от $s$, используя для веса формулу с потенциалами, записать их в $d$.
• • Протолкнуть максимально возможный поток вдоль кратчайшего пути $s⇝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(Um\log n)$ или $O(U{n}^2)$ в случае плотных графов.

В наиболее популярных задачах рёбра обычно с единичной пропускной способностью, и $U\le n$ или $U\le m$. Например, в задаче о назначениях $U=n$, и алгоритм работает за $O(n^3)$, что совпадает с асимптотикой венгерского алгоритма.