Изменения

Пусть существует граф <tex>G</tex> и <tex>\forall (u,v)\in E\colon c_{(u,v)}\in\mathbb N</tex>. Суть алгоритма в нахождении сперва путей с высокой пропускной способностью, чтобы сразу сильно увеличивать поток по этим путям, а затем всех остальныхпо всем остальным. Пусть <tex>U</tex> - максимальная пропускная способность. Введём параметр <tex>\Delta = 2^{\lfloor\log_2U\rfloor}</tex>. На каждом шаге будем искать в остаточном графе увеличивающие пути с пропускной способностью не меньше, чем <tex>\Delta</tex>, и увеличивать поток вдоль этих путей. В конце шага будем уменьшать <tex>\Delta</tex> в два раза, и на следующем шаге будем искать увеличивающий путь с новым значением параметра. При значении <tex>\Delta</tex>, равном единице, данный алгоритм становится идентичен [[Алоритм_Эдмондса-Карпа | алгоритму Эдмондса — Карпа]]. Из этого следует, что алгоритм корректен.