272
правки
Изменения
→Алгоритм
На каждой итерации в [[Дополняющая_сеть,_дополняющий_путь|дополняющей сети]] находим дополняющие пути с пропускной способностью не меньшей <tex> \Delta </tex>, увеличиваем поток вдоль них.
Уменьшив масштаб <tex> \Delta </tex> в <tex> 2 </tex> раза, переходим к следующей итерации.
Заметим, что при <tex> \Delta = 1 </tex> алгоритм вырождается в алгоритм [[Алоритм_Эдмондса-Карпа|Эдмондса-Карпа]], вследствие чего является корректным.
Количество необходимых дополнений путей, основанных на кратчайших путях, может быть много больше количества дополнений, основанных на путях с высокой пропускной способностью.
