Задача о потоке минимальной стоимости состоит в нахождении самого дешёвого способа передачи потока определённой величины через транспортную сеть .

Определения

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

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

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

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

Ограничение пропускной способности :	${\displaystyle 0\leqslant f(u,v)\leqslant 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}$ .

Примечательно, что для ${\displaystyle d=1}$ , задача нахождения потока минимальной стоимости соответствует задаче о поиске кратчайшего пути . В случае же, когда стоимость ${\displaystyle a(e)=0}$ для всех рёбер графа, задача может быть решена адаптированными алгоритмами поиска максимального потока:

1. Как только ${\displaystyle |f|\geqslant d}$ впервые, останови алгоритм.
2. Пусть ${\displaystyle p}$ величина последнего дополнения потока.
3. Замени последний поток на поток со значением ${\displaystyle p-(|f|-d)}$ .

Существует также и альтернативный вариант решения задачи с нулевой стоимостью рёбер:

1. Создай новую вершину-источник ${\displaystyle s'}$ .
2. Добавь ребро ${\displaystyle e'=(s',s)}$ с пропускной способностью ${\displaystyle c(e')=d}$ .
3. Таким образом максимальный поток будет ограничен ${\displaystyle d}$ .

Решения

• Задача о потоке минимальной стоимости может быть решена с помощью линейного программирования .
• Найти любой поток данной величины, после чего избавиться от всех циклов отрицательной стоимости в остаточном графе. Чтобы избавиться от цикла, надо пустить по нему максимально возможный поток. Циклы ищутся алгоритмом Беллмана - Форда . Для доказательства работы алгоритма покажем, что поток ${\displaystyle f}$ графа ${\displaystyle G}$ не является потоком минимальной стоимости пока остаточная сеть графа ${\displaystyle G_{f}}$ содержит отрицательный цикл ${\displaystyle C}$ . Пусть ${\displaystyle f^{*}}$ - поток графа ${\displaystyle G}$ такой, что ${\displaystyle l(f^{*})<l(f)}$ и, следовательно, оба потока отличны друг от друга. Для всех рёбер ${\displaystyle e\in E}$ обозначим ${\displaystyle f'(e)=f^{*}(e)-f(e)}$ и получим ${\displaystyle f'}$ - циклический поток. Так как ${\displaystyle f'}$ образован из максимум ${\displaystyle m'<m}$ циклов ${\displaystyle f'_{i}}$ ${\displaystyle (1\leqslant i\leqslant m')}$ , справедливо следующее: ${\displaystyle l(f')=l(f^{*})-l(f)=\sum _{1\leqslant i\leqslant m'}l(f'_{i})}$ , а значит, существует такой ${\displaystyle j}$ , что ${\displaystyle l(f'_{j})<0}$ . Для оптимизиации алгоритма можно выбирать каждую итерацию циклы с минимальной средней стоимостью ${\displaystyle {\overline {l}}(C)={\frac {l(C)}{|C|}}={\frac {\sum _{e\in C}l(e)}{|C|}}}$ . Для доказательства времени работы алгоритма разобьем ход его выполнения на фазы, каждая из которых будет состоять из отдельных итераций. Пусть ${\displaystyle f}$ - поток к началу ${\displaystyle i}$ -той фазы. Фаза ${\displaystyle i}$ считается завершенной, когда найден поток ${\displaystyle g}$ такой, что ${\displaystyle \mu (g)\leqslant (1-1/n)\cdot \mu (f)}$ или ${\displaystyle \mu (g)\leqslant 0}$ , где ${\displaystyle \mu (f)=-{\overline {l}}(C)}$ . При ${\displaystyle \mu (g)\leqslant 0}$ алгоритм прекращает работу. Далее пусть ${\displaystyle \mu _{0}}$ - значение ${\displaystyle \mu }$ к началу первой фазы и ${\displaystyle \mu _{i}}$ - значение ${\displaystyle \mu }$ к началу ${\displaystyle i}$ -той фазы ( ${\displaystyle 1\leqslant i\leqslant T}$ ). Таким образом действительно: ${\displaystyle \mu _{i}\leqslant (1-1/n)\cdot \mu _{i-1}\leqslant {\frac {\mu _{i-1}}{e^{1/n}}}}$ , а также ${\displaystyle \mu _{0}\leqslant L=\sum _{e\in E}|l(e)|}$ . Вследствие свойства целочисленности ${\displaystyle \mu _{T-1}\geqslant 1/n}$ следует ${\displaystyle T-1\leqslant \log _{e^{1/n}}(nL)={\frac {\ln(nL)}{\ln(e^{1/n})}}=n\ln(nL)}$ и ${\displaystyle T\leqslant n\ln(nL)+1}$ . Итерации условно можно разбить на несколько видов: Тип 1 - цикл ${\displaystyle C}$ содержит только рёбра с негативной стоимостью и Тип 2 - цикл ${\displaystyle C}$ содержит минимум одно ребро с положительной стоимостью. При каждой итерации первого типа будет "насыщено" и удалено хотя бы одно ребро. При этом все образованные рёбра будут иметь положительную стоимость (так как имеют обратное направление в остаточной сети). Таким образом алгоритм завершится после как минимум ${\displaystyle m}$ последовательных итераций первого типа. Если же в фазе содержатся более ${\displaystyle m}$ итераций, после ${\displaystyle m-1}$ итераций максимум будет выполнена итерация второго типа. Покажем однако, что такое невозможно: Пусть ${\displaystyle g}$ - поток первой итерации второго типа. Заметим, что действительно ${\displaystyle \forall e\in E(G_{g}):l(e)\geqslant -\mu (f)}$ , т.е. нет новых рёбер с отрицательной стоимостью. Пусть ${\displaystyle C}$ - цикл в ${\displaystyle G_{g}}$ с минимальным ${\displaystyle {\overline {l}}(C)}$ и ${\displaystyle H}$ - рёбра с отрицательной стоимостью в ${\displaystyle C}$ : ${\displaystyle \mu (g)=\sum _{e\in C}{\frac {-l(e)}{|C|}}\leqslant \sum _{e\in H}{\frac {-l(e)}{|C|}}\leqslant |H|\cdot {\frac {\mu (f)}{|C|}}}$ . Из ${\displaystyle |H|\leqslant |C|-1}$ следует ${\displaystyle |H|/|C|\leqslant 1-1/|C|\leqslant 1-1/n}$ . Таким образом ${\displaystyle \mu (g)\leqslant (1-1/n)\cdot \mu (f)}$ . Противоречие - мы уже достигли конца фазы, а значит итераций второго типа не существует и каждая фаза заканчивается через ${\displaystyle m-1}$ итераций первого типа. Цикл с минимальным средним весом может быть найден за ${\displaystyle O(|V||E|)}$ . Доказательство: Пусть ${\displaystyle d_{k}(v)}$ - стоимость самого выгодного пути к ${\displaystyle v\in V}$ через ровно ${\displaystyle k}$ рёбер, тогда действительно ${\displaystyle d_{0}(v)=0}$ и ${\displaystyle d_{k+1}(v)=\min _{e=(w,v)\in E_{f}}(d_{k}(w)+l(e))}$ . Выходит, что все значения ${\displaystyle d_{k}(v)}$ можно подсчитать за ${\displaystyle O(nm)}$ используя динамическое программирование . Лемма: Значение ${\displaystyle {\overline {l}}(C)}$ цикла с минимальной средней стоимостью равно ${\displaystyle \alpha =\min _{v\in V}\max _{j=0}^{n-1}({\frac {d_{n}(v)-d_{j}(v)}{n-j}})}$ . Пусть ${\displaystyle C}$ - цикл с минимальной средней стоимостью. Если увеличить стоимость всех рёбер на ${\displaystyle \delta }$ , то ${\displaystyle C}$ останется циклом с минимальной средней стоимостью, однако значение цикла увеличится на ${\displaystyle \delta }$ . таким образом можно увеличить все стоимости рёбер так, что ${\displaystyle {\overline {l}}(C)=0}$ . Покажем, что ${\displaystyle \alpha \geqslant 0}$ : Выеберем любую вершину ${\displaystyle v}$ и путь ${\displaystyle P}$ , заканчивающийся в ${\displaystyle v}$ и имеющий стоимость ${\displaystyle d_{n}(v)}$ . ${\displaystyle P}$ должен содержать цикл ${\displaystyle C}$ . Пусть ${\displaystyle P'}$ - путь ${\displaystyle P}$ не содержащий цикла ${\displaystyle C}$ и имеющий длину ${\displaystyle j}$ . Тогда в цикле имеется ${\displaystyle n-j}$ рёбер. Из-за ${\displaystyle l(C)\geqslant 0}$ справедливо ${\displaystyle d_{n}(v)=l(P)=l(C)+l(P')\geqslant l(P')\geqslant d_{j}(v)}$ и для каждой вершины ${\displaystyle v}$ существует ${\displaystyle j\in \{1,...,n-1\}}$ такой, что ${\displaystyle d_{n}(v)\geqslant d_{j}(v)}$ . Покажем, что ${\displaystyle \alpha \leqslant 0}$ : Для этого докажем, что существует вершина ${\displaystyle w}$ для которой истино ${\displaystyle d_{n}(w)\leqslant d_{j}(w)}$ для всех ${\displaystyle j\in \{1,...,n-1\}}$ . Пусть ${\displaystyle v}$ - вершина цикла с минимальной средней стоимостью ${\displaystyle C}$ , ${\displaystyle P}$ - кратчайший путь, заканчивающийся на ${\displaystyle v}$ и не содержащий в себе цикла. пусть ${\displaystyle p<n}$ количество вершин в ${\displaystyle P}$ . Также ввёдем вершину ${\displaystyle w}$ , которая лежит на ${\displaystyle C}$ на расстоянии ${\displaystyle n-p}$ вершин от ${\displaystyle v}$ . Путь от ${\displaystyle v}$ к ${\displaystyle w}$ назовём ${\displaystyle Q}$ . Пусть ${\displaystyle R}$ - путь из ${\displaystyle w}$ к ${\displaystyle v}$ , а ${\displaystyle S}$ - путь минимальной длины ${\displaystyle j}$ из источника графа к ${\displaystyle w}$ . Тогда истино следующее: ${\displaystyle d_{n}(w)\leqslant l(P)+l(Q)=d_{p}(v)+l(Q)}$ , а также ${\displaystyle d_{p}(v)\leqslant d_{j+r}(v)\leqslant d_{j}(w)+l(R)}$ и из них следует, что ${\displaystyle d_{n}(w)\leqslant d_{j}(w)+l(R)+l(Q)}$ . Путь ${\displaystyle Q\odot R}$ имеет стоимость 0, т.к. ${\displaystyle l(C)=0}$ . Таким образом ${\displaystyle d_{n}(w)\leqslant d_{j}(w)}$ для всех ${\displaystyle j\in \{1,...,n-1\}}$ . Учитывая лемму, получим ${\displaystyle \alpha \leqslant 0}$ . Время выполнения такого алгоритам составит ${\displaystyle O(m^{2}\cdot n^{2}\cdot \log(nL))}$ , так как в процессе выполнения алгоритма пройдут ${\displaystyle n\log(nL)+1}$ фаз, в каждой из которых ${\displaystyle m}$ итераций, требующих ${\displaystyle O(nm)}$ времени. Основываясь не предидущей оценке времени можно составить и следующую: ${\displaystyle O(m^{3}\cdot n^{2}\cdot \log(n))}$ .
• Использовать модификацию алгоритма Форда — Фалкерсона , в которой на каждом шаге выбирается увеличивающий путь минимальной цены. Для выбора пути можно воспользоваться алгоритмом Беллмана-Форда.
• Улучшение предыдущего алгоритма: используя потенциалы, можно свести задачу к задаче без отрицательных рёбер, после чего вместо алгоритма Беллмана-Форда воспользоваться алгоритмом Дейкстры . Алгоритм Беллмана-Форда придётся применить лишь на самом первом шаге.

Ссылки

См. также

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

Литература

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