322
правки
Изменения
→Корректность алгоритма
Покажем, что если алгоритм завершается, то на выходе у него получается поток именно максимальной величины.
В самом деле, предположим, что в какой-то момент во вспомогательной сети, построенной для остаточной сети, не удалось найти блокирующий поток. Это означает, что сток вообще не достижим во вспомогательной сети из истока . Но поскольку она содержит в себе все кратчайшие пути из истока в остаточной сети, это в свою очередь означает, что в остаточной сети нет пути из истока в сток. Следовательно, применяя [[Теорема Форда-Фалкерсона|теорему Форда-Фалкерсона]], получаем, что текущий поток в самом деле максимален.
=== Ассимптотика алгоритма ===
