Изменения

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

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

183 байта добавлено, 14:08, 24 января 2016
Алгоритмы решения
}}
=== Алгоритмы решения ===
* Воспользуемся [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети|леммой об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]].
** Найдем любой поток величины <tex>f_0</tex>.
** При помощи [[Алгоритм Форда-Беллмана|Форда-Беллмана]] найдем отрицательные циклы в остаточной сети.
** Избавимся от всех найденных циклов, для этого, пустим по ним максимально возможный поток.
===Метод дополнения потока вдоль путей минимальной стоимости===*[[Поиск_потока_минимальной_стоимости_методом_дополнения_вдоль_путей_минимальной_стоимости|Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]].*===Использование потенциалов Джонсона===[[Использование_потенциалов_Джонсона_при_поиске_потока_минимальной_стоимости|Использование потенциалов Джонсона при поиске потока минимальной стоимости (модификация предыдущего алгоритма)]].
== См. также ==
147
правок

Навигация