Изменения

На каждом первом шаге алгоритм выполняет в худшем случае <tex>O(E)</tex> увеличений потока. Докажем это. Пусть <tex>\Delta = 2^k</tex>. В конце шага множество вершин графа можно разбить на две части: <tex>A_k</tex> и <tex>\overline{A_k}</tex>. Все рёбра, выходящие из <tex>A_k</tex>, ребра имеют остаточную пропускную способность менее <tex>2^k</tex>. Наибольшее количество рёбер между <tex>A_k</tex> и <tex>\overline{A_k}</tex> равно <tex>E</tex>. Следовательно, остаточный поток (поток, который может быть получен на оставшихся шагах) на фазе с текущим значением <tex>k</tex> максимально составляет <tex>2^kE</tex>. Каждый увеличивающий путь при данном <tex>k</tex> имеет пропускную способность как минимум <tex>2^k</tex>. На предыдущем шаге, с масштабом <tex>k+1</tex>, остаточный поток ограничен <tex>2^{k+1}E</tex>. Значит максимальное число появившихся увеличивающих путей равно , <tex>2E|f_0| \leq |VG| </tex>. Увеличивающий путь можно найти за Поиск каждого дополнительного пути занимает <tex>O(E)</tex>, используя [[Обход_в_ширину | BFS]]. Количество шагов а их количество не больше <tex>O(\log_2U)V </tex>. Итоговая сложность первой итерации — <tex>O(VE) \leq O(E^2\log_2U)</tex>.