Изменения

Перейти к: навигация, поиск

Поток минимальной стоимости

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

Навигация