6
правок
Изменения
→Алгоритм: Оказывается бывают отрицательные стоимости
* '''Шаг 1'''. Определим для каждого прямого ребра <tex>(u,v)</tex> обратное ребро <tex>(v,u)</tex>. Определим его характеристики: <tex>c(v,u)=0</tex>, <tex>f(v,u)=-f(u,v)</tex>, <tex>a(v,u)=-a(u,v)</tex>.
* '''Шаг 2'''. Для каждого ребра зададим поток равный <tex>0</tex>.
* '''Шаг 3'''. Найдем произвольный максимальный поток(любым алгоритмом нахождения максимального потока), построим для него остаточную сеть, где каждому ребру будет соответствовать величина <tex>a(u,v) \cdot (c(u,v) - f(u,v))</tex>. Таким образом обратные ребра в остаточной сети будут иметь неположительную стоимость.
* '''Шаг 4'''. При помощи [[Алгоритм Форда-Беллмана| алгоритма Форда-Беллмана]] найдем отрицательный цикл в построенной сети. Если отрицательный цикл не нашелся {{---}} перейдем к '''шагу 6'''.
* '''Шаг 5'''. Избавимся от отрицательного цикла, для этого пустим по нему максимально возможный поток. Величина потока равна минимальной остаточной пропускной способности в цикле. Перейдем к '''шагу 4'''.
====Асимптотика====
Алгоритм Форда-Беллмана работает за <tex>O(VE)</tex>, улучшение цикла работает за <tex>O(E)</tex>. Если обозначить максимальную стоимость потока как <tex>C</tex>, а максимальную пропускную способность как <tex>U</tex>, то алгоритм совершит <tex>O(ECU)</tex> итераций поиска цикла, если каждое улучшение цикла будет улучшать его на 1. В итоге имеем <tex>O(V E^2 C U + maxFlow)</tex>, где <tex>maxFlow</tex> - асимптотика поиска максимального потока.
===Метод дополнения потока вдоль путей минимальной стоимости===
{{main|Поиск_потока_минимальной_стоимости_методом_дополнения_вдоль_путей_минимальной_стоимостиПоиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости}}
===Использование потенциалов Джонсона===
{{main|Использование_потенциалов_Джонсона_при_поиске_потока_минимальной_стоимостиИспользование потенциалов Джонсона при поиске потока минимальной стоимости}}
== См. также ==
