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

Дана транспортная сеть ${\displaystyle G(V,E)}$ с источником ${\displaystyle s\in V}$ и стоком ${\displaystyle t\in V}$, где рёбра ${\displaystyle (u,v)\in E}$ имеют пропускную способность ${\displaystyle c(u,v)}$, поток ${\displaystyle f(u,v)}$ и цену ${\displaystyle a(u,v)}$. Цена пересылки потока ${\displaystyle f(u,v)\cdot a(u,v)}$. Необходимо переслать ${\displaystyle d}$ единиц потока.

Суть задачи — найти поток f(u, v), минимизирующий его общую стоимость:

${\displaystyle \sum _{u,v\in V}a(u,v)\cdot f(u,v)}$

Накладываются следующие условия:

Ограничение пропускной способности:	${\displaystyle \ f(u,v)\leq c(u,v)}$. Поток не может превысить пропускную способность.
Антисимметричность:	${\displaystyle \ f(u,v)=-f(v,u)}$. Поток из ${\displaystyle \ u}$ в ${\displaystyle \ v}$ должен быть противоположным потоку из ${\displaystyle \ v}$ в ${\displaystyle \ u}$.
Сохранение потока:	${\displaystyle \ \sum _{w\in V}f(u,w)=0}$.
Необходимый поток:	${\displaystyle \sum _{w\in V}f(s,w)=d}$

Другой вариант этой задачи — найти максимальный поток имеющий минимальную цену среди максимальных.

Более общая проблема — циркуляция потока минимальной стоимости, которая может быть использована для решения данной задачи. Ставим нижнюю границу для всех рёбер равную нулю и проводим дополнительное ребро из стока ${\displaystyle t}$ в источник ${\displaystyle s}$ с пропускной способностью ${\displaystyle c(t,s)=d}$ и нижней границей ${\displaystyle l(t,s)=d}$.

• Задача о потоке минимальной стоимости может быть решена с помощью линейного программирования.
• Найти любой поток данной величины, после чего избавиться от всех циклов отрицательной стоимости в остаточном графе. Чтобы избавиться от цикла, надо пустить по нему максимально возможный поток. Циклы ищутся алгоритмом Беллмана - Форда.
• Использовать модификацию алгоритма Форда — Фалкерсона, в которой на каждом шаге выбирается увеличивающий путь минимальной цены. Для выбора пути можно воспользоваться алгоритмом Беллмана-Форда.
• Улучшение предыдущего алгоритма: используя потенциалы, можно свести задачу к задаче без отрицательных рёбер, после чего вместо алгоритма Беллмана-Форда воспользоваться алгоритмом Дейкстры. Алгоритм Беллмана-Форда придётся применить лишь на самом первом шаге.

• Визуализатор алгоритма нахождения максимального потока минимальной стоимости

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

• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4.