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