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'''.
===Метод дополнения потока вдоль путей минимальной стоимости===
{{main|Поиск_потока_минимальной_стоимости_методом_дополнения_вдоль_путей_минимальной_стоимостиПоиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости}}
===Использование потенциалов Джонсона===
{{main|Использование_потенциалов_Джонсона_при_поиске_потока_минимальной_стоимостиИспользование потенциалов Джонсона при поиске потока минимальной стоимости}}
== См. также ==
