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