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

==Теорема Форда-Фалкерсона==
Задача о потоке минимальной стоимости состоит в нахождении среди всех [[Определение сети, потока|потоков]] данной величины наименее затратного.

{{Лемма
|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>. Таким образом, поток через каждое ребро не превосходит пропускной способности остаточной сети. 
Антисимметричность и закон сохранения потока проверяются аналогично [[Лемма о сложении потоков|лемме о сложении потоков]].
}}

{{Теорема
|statement=
Пусть: <tex> G </tex> {{---}} сеть с истоком <tex> s </tex> и стоком <tex> t </tex>, <tex> f </tex> {{---}} поток минимальной стоимости в сети <tex> G </tex>  среди потоков величины <tex> a </tex>, <tex> P </tex> {{---}} путь минимальной стоимости <tex> s \leadsto t</tex> в остаточной сети.
Тогда:
<tex>\forall \delta : 0 \leqslant \delta \leqslant c_f(P)</tex> поток <tex>f + \delta \cdot f_P</tex> {{---}} поток минимальной стоимости среди потоков величины <tex>a + \delta</tex>, где <tex>\delta \cdot f_P</tex> {{---}} поток величины <tex>\delta</tex>, проходящий по пути <tex>P</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'''. Поток минимальной стоимости найден, т.к в остаточной сети не осталось ни одного пути.
* Конец.

===Реализация===

 '''for''' <tex>e \in E</tex> {
      <tex>f[e] \leftarrow 0</tex>
 }
 '''while''' (существует путь <tex>s \leadsto t</tex> в остаточной сети <tex>G_f</tex>) {
       <tex>P \leftarrow</tex> кратчайший в смысле стоимости путь <tex>s \leadsto t</tex>
       дополнить поток <tex>f</tex> вдоль <tex>P</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)

[[Категория:Алгоритмы и структуры данных]]
[[Категория: Задача о потоке минимальной стоимости]]
@@ Строка 30: / Строка 30: @@
 ==Алгоритм==
-На основании теоремы построим алгоритм. На каждой итерации алгоритма будем находить путь минимальной стоимости из <tex>s</tex> в <tex>t</tex> в остаточной сети и дополнять поток вдоль него. Выбирать алгоритм для поиска кратчайших путей следует с учетом того, что в ходе алгоритма появляются ребра отрицательного веса.
+На основании теоремы построим алгоритм.. На каждой итерации алгоритма будем находить путь минимальной стоимости из <tex>s</tex> в <tex>t</tex> в остаточной сети и дополнять поток вдоль него. Выбирать алгоритм для поиска кратчайших путей следует с учетом того, что в ходе алгоритма появляются ребра отрицательного веса.
 ===Описание===
@@ Строка 44: / Строка 44: @@
 ===Реализация===
-Пусть задана структура <tex>Edge</tex>:
+  '''for''' <tex>e \in E</tex> {
-  '''struct''' edge:
+      <tex>f[e] \leftarrow 0</tex>
-    '''int''' from
+ }
-    '''int''' to
+ '''while''' (существует путь <tex>s \leadsto t</tex> в остаточной сети <tex>G_f</tex>) {
-    '''double''' c       <font color=green>// пропускная способность ребра</font>
+       <tex>P \leftarrow</tex> кратчайший в смысле стоимости путь <tex>s \leadsto t</tex>
-    '''double''' flow    <font color=green>// поток через ребро</font>
+       дополнить поток <tex>f</tex> вдоль <tex>P</tex>
-    '''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>
 ===Асимптотика===
@@ Строка 75: / Строка 63: @@
 ==Источники информации==
 *[https://ru.wikipedia.org/wiki/Теорема_Форда_—_Фалкерсона Wikipedia {{---}} Теорема Форда-Фалкерсона]
+== Литература ==
 * Ravindra Ahuja, Thomas Magnanti, James Orlin. Network flows (1993)
 [[Категория:Алгоритмы и структуры данных]]
 [[Категория: Задача о потоке минимальной стоимости]]