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