147
правок
Изменения
→Реализация
==Идея==В основе алгоритма лежит [[Теорема Форда-Фалкерсона ==Задача о потоке минимальной стоимостисостоит в нахождении среди всех [[Определение сети, потока|теорема Форда-Фалкерсона о потоке минимальной стоимостипотоков]]. На каждой итерации алгоритма будем находить путь из <tex>s</tex> в <tex>t</tex> минимальной стоимости и дополнять поток вдоль этого пути.У нас появляются ребра отрицательного веса. Выбирать алгоритм для поиска кратчайших путей следует с учетом этого фактаданной величины наименее затратного.
{{Лемма|about=о представлении потоков|statement=РеализацияПусть <tex> f </tex> и <tex> g </tex> {{---}} потоки в сети <tex> G </tex>. Тогда <tex> g </tex> можно представить как сумму <tex> f + f'</tex>, где <tex>f'</tex> {{---}} поток в остаточной сети <tex>G_f</tex>.|proof=Рассмотрим произвольное ребро <tex> (u, v) </tex> из <tex> G </tex>. <tex> f'(u, v) =g(u, v) - f(u, v) \leqslant c(u, v) - f(u, v) = c_f(u, v) </tex>. Таким образом, поток через каждое ребро не превосходит пропускной способности остаточной сети. Антисимметричность и закон сохранения потока проверяются аналогично [[Лемма о сложении потоков|лемме о сложении потоков]].}}
|proof=Пусть <tex> g </tex> {{---}} поток минимальной стоимости величины <tex>a + \delta</tex> в <tex>G</tex>. Представим <tex> g =Корректность==Непосредственно следует из f + f'</tex>, где <tex> f' </tex> {{---}} поток в остаточной сети <tex>G_f</tex>. Тогда разность <tex> g - f</tex> будет потоком в сети <tex>G_f</tex> и по [[Теорема Форда-Фалкерсона Лемма о потоке минимальной стоимостисложении потоков|теоремы Форда-Фалкерсона лемме о потоке минимальной стоимостисложении потоков]]его величина будет равна <tex>\delta</tex>.
По [[Теорема о декомпозиции|теореме о декомпозиции]] <tex> g - f</tex> можно представить как сумму элементарных потоков вдоль путей <tex>P_i : s \leadsto t</tex> и циклов <tex>C_i</tex>. В этом представлении нет отрицательных циклов, иначе прибавление его к <tex> f </tex> даст поток меньшей стоимости. Если есть положительный цикл, то вычтем его из <tex> g </tex> и получим поток меньшей стоимости. Таким образом, <tex>p(C_i) = 0</tex> для всех циклов. Тогда <tex>p(g - f) = \sum\limits_{P_i} p(P_i)\cdot c_f(P_i) \geqslant p(P) \cdot \sum\limits_{P_i}c_f(P_i) \geqslant p(P) \cdot \delta</tex>. Отсюда <tex> p(g) \geqslant p(f) + p(P) \cdot \delta \geqslant p(g) </tex> и поток <tex>f + \delta \cdot f_P</tex> {{---}} минимальный. }} ==Алгоритм==На основании теоремы построим алгоритм. На каждой итерации алгоритма будем находить путь минимальной стоимости из <tex>s</tex> в <tex>t</tex> в остаточной сети и дополнять поток вдоль него. Выбирать алгоритм для поиска кратчайших путей следует с учетом того, что в ходе алгоритма появляются ребра отрицательного веса. ===Описание===* Начало.* '''Шаг 1'''. Для каждого ребра зададим поток равный <tex>0</tex>.* '''Шаг 2'''. Построим остаточную сеть <tex>G_f</tex>.* '''Шаг 3'''. Если существует путь <tex>s \leadsto t</tex> в остаточной сети <tex>G_f</tex> {{---}} перейдем к '''шагу 4''', иначе к '''шагу 6'''.* '''Шаг 4'''. Найдем путь <tex>s \leadsto t</tex> c минимальной стоимостью: путь <tex> P</tex>.* '''Шаг 5'''. Дополним поток <tex>f</tex> вдоль пути <tex>P</tex>.* '''Шаг 6'''. Поток минимальной стоимости найден, т.к в остаточной сети не осталось ни одного пути.* Конец. ===Реализация=== Пусть задана структура <tex>Edge</tex>: '''struct''' edge: '''int''' from '''int''' to '''double''' c <font color=green>// пропускная способность ребра</font> '''double''' flow <font color=green>// поток через ребро</font> '''double''' price <font color=green>// стоимость перемещения единицы потока через ребро</font> Будем использовать структуру для хранения ребер графа G. '''Edge[]''' findMinCostMaxFlow(<tex>G: (V, E)</tex>, '''int''' s, '''int''' t): '''for''' edge '''in''' <tex>E</tex>: edge.flow = 0 '''while''' <tex>\exists</tex> путь <tex>s \leadsto t</tex> в остаточной сети <tex>G_f</tex>: P = путь <tex>s \leadsto t</tex> с наименьшей стоимостью. maxFlow = <tex>\displaystyle \min_{edge \in P} edge.c - edge.flow</tex> '''for''' edge '''in''' P: edge.flow += maxFlow '''return''' <tex>E</tex> ===Асимптотика===
Каждая итерация выполняется за время работы поиска кратчайшего пути, обозначим его <tex>F(V, E)</tex>. В сетях с целочисленной пропускной способностью итераций будет не более <tex>|f|</tex>.
Итого получаем время работы <tex>O(F(V, E) \cdot |f|)</tex>.
== Литература См. также==*[[Поток минимальной стоимости| Поток минимальной стоимости]]*[[Использование потенциалов Джонсона при поиске потока минимальной стоимости| Использование потенциалов Джонсона при поиске потока минимальной стоимости]] ==Источники информации==*[https://ru.wikipedia.org/wiki/Теорема_Форда_—_Фалкерсона Wikipedia {{---}} Теорема Форда-Фалкерсона]
* Ravindra Ahuja, Thomas Magnanti, James Orlin. Network flows (1993)
[[Категория:Алгоритмы и структуры данных]]
[[Категория: Задача о потоке минимальной стоимости]]
