147
правок
Изменения
→Алгоритм
* '''Шаг 2'''. Для каждого ребра зададим поток равный 0.
* '''Шаг 3'''. Построим остаточную сеть <tex>G_f</tex>.
* '''Шаг 4'''. При помощи [[Алгоритм Форда-Беллмана| алгоритма Форда-Беллмана]] найдем отрицательный цикл отрицательные циклы в остаточной сети. Если нет - перейдем к '''шагу 7'''.* '''Шаг 5'''. Выберем один из отрицательных циклов.* '''Шаг 6'''. Избавимся от отрицательного цикла, для этого пустим по нему максимально возможный поток.* '''Шаг 6'''. Перейдем к '''шагу 35'''.
* '''Шаг 7'''. Отрицательных циклов восточной сети нет, значит, максимальный поток минимальной стоимости найден.
* '''Конец.'''
====Ассимптотика====
Алгоритм Форда-Беллмана работает за <tex>O(VE)</tex>. Нахождение максимального потока и улучшение цикла работает за <tex>O(E)</tex>. В итоге имеем <tex>O(V E^2)</tex>.
