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

Задача о потоке минимальной стоимости

Определение:

Пусть дана сеть $G(V,E)$. $S, T \in V$ — источник и сток. Ребра $(u,v) \in E$ имееют пропускную способность $c(u, v),$ поток $f(u,v)$ и цену за единицу потока $a(u, v)$. Тогда общая стоимость потока из $S$ в $T$: $p(u,v) = \sum\limits_{u,v \in V, f(u,v)\gt 0} a(u,v) \cdot f(u,v)$

Свойства сети

• Поток не может превысить пропускную способность.

$f(u,v) \leqslant c(u,v)$

• Поток из $u$ в $v$ должен быть противоположным потоку из $v$ в $u$.

$f(u, v)=-f(v, u)$

• Сохранение потока. Для каждой вершины, сумма входящего и исходящего потоков равно $0$.

$\sum\limits_{w \in V} f(u,w) = 0$

Задача:

Дана сеть $G(V,E)$. $S, T \in V$ — источник и сток. Ребра $(u,v) \in E$ имееют пропускную способность $c(u, v),$ поток $f(u,v)$ — и цену за единицу потока $a(u, v)$. Требуется найти максимальный поток, суммарная стоимость которого минимальна.

Алгоритмы решения

Метод устранения отрицательных циклов в остаточной сети

Воспользуемся леммой об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети. Получим следующий алгоритм:

Алгоритм

• Начало.
• Шаг 1. Определим для каждого прямого ребра $(u,v)$ обратное ребро $(v,u)$. Определим его характеристики: $c(v,u)=0$, $f(v,u)=-f(u,v)$, $a(v,u)=-a(u,v)$.
• Шаг 2. Для каждого ребра зададим поток равный $0$.
• Шаг 3. Найдем произвольный максимальный поток(любым алгоритмом нахождения максимального потока), построим для него остаточную сеть, где каждому ребру будет соответствовать величина $a(u,v) \cdot (c(u,v) - f(u,v))$.
• Шаг 4. При помощи алгоритма Форда-Беллмана найдем отрицательный цикл в построенной сети (отрицательный цикл ищется по стоимости ребра, т.е. ребра имеют вес $a(u,v)$). Если отрицательный цикл не нашелся — перейдем к шагу 6.
• Шаг 5. Избавимся от отрицательного цикла, для этого пустим по нему максимально возможный поток. Величина потока равна минимальной остаточной пропускной способности в цикле. Перейдем к шагу 4.
• Шаг 6. Отрицательных циклов в остаточной сети нет, значит, максимальный поток минимальной стоимости найден.
• Конец.

Асимптотика

Алгоритм Форда-Беллмана работает за $O(VE)$, улучшение цикла за $O(E)$. Если обозначить максимальную стоимость потока как $C$, а максимальную пропускную способность как $U$, то алгоритм совершит $O(ECU)$ итераций поиска цикла, если каждое улучшение цикла будет улучшать его на 1. В итоге имеем $O(V E^2 C U + maxFlow)$, где $maxFlow$ - асимптотика поиска максимального потока.

См. также

• Сведение задачи о назначениях к задаче о потоке минимальной стоимости
• Венгерский алгоритм решения задачи о назначениях

Источники информации

• Википедия — Поток минимальной стоимости
• Визуализатор алгоритма нахождения максимального потока минимальной стоимости
• Хабрахабр — Максимальный поток минимальной стоимости
• Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)