Изменения

На каждом шаге алгоритм выполняет <tex>O(E)</tex> увеличений потока в худшем случае (т.кДокажем это. <tex>\Delta = 2^k</tex>. Каждый увеличивающий путь при данном <tex>k</tex> имеет пропускную способность как минимум <tex>2^k</tex>. минимальный разрез на каждом На предыдущем шаге меньше, чем с масштабом <tex>k+1</tex> поток был ограничен <tex>2^{k+1}E</tex>. Значит максимальное число появившихся увеличивающих путей равно <tex>2E\Delta</tex>). Дополняющий путь можно найти за <tex>O(E)</tex> , используя [[Обход_в_ширину | BFS]]. Количество шагов <tex>O(log_2U)</tex>. Итоговая сложность <tex>O(E^2log_2U)</tex>.