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

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

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

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

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

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

[math]f(u,v) \leqslant c(u,v)[/math]

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

[math]f(u, v)=-f(v, u)[/math]

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

[math] \sum\limits_{w \in V} f(u,w) = 0[/math]

Задача:

Дана сеть [math]G(V,E)[/math]. [math]S, T \in V[/math] — источник и сток. [math]\forall (u,v) \in E[/math] [math]\exists c(u, v), f(u,v)[/math] — стоимость пересылки единицы потока и пропускная способность. Требуется найти максимальный поток, суммарная стоимость которого минимальна.

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

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

• Воспользуемся леммой об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети.
  • Найдем любой поток величины [math]f_0[/math].
  • При помощи Форда-Беллмана найдем отрицательные циклы в остаточной сети.
  • Избавимся от всех найденных циклов, для этого, пустим по ним максимально возможный поток.

Метод дополнения потока вдоль путей минимальной стоимости

Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости.

Использование потенциалов Джонсона

Использование потенциалов Джонсона при поиске потока минимальной стоимости (модификация предыдущего алгоритма).

См. также

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

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

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