Изменения

Время работы Сложность алгоритма — <tex> O(E^2 \log U) </tex>.

Количество итераций — <tex> O(\log U) </tex>. Докажем, что сложность каждой итерации — <tex> O(E^2) </tex>.

{{Лемма|statement=Сложность первой итерации алгоритма — <tex> O(E^2) </tex>.|proof=На первом шаге ребра имеют пропускную способность <tex> 1 </tex>. Значит, <tex> |f_0| \leq |VG| V </tex>. Поиск каждого дополнительного пути требует <tex> O(E) </tex> времени, а их количество не больше <tex> V </tex>. Итоговая сложность первой итерации — <tex> O(VE) \leq O(E^2) </tex>, q.e.d.}}

Граф <tex> G_{f_0} </tex> — несвязен. Пусть <tex> A </tex> — компонента связности, <tex> s \in A, t \in \overline{A} </tex>. Тогда <tex> c_{0_{f_0}}(A, \overline{A}) = 0 </tex>.  Значит, в графе с пропускными способностями <tex> c_1 </tex>:

<tex> \langle A, \overline{A} \rangle </tex> — разрез. Рассмотрим максимальный поток <tex> f'_1 </tex> в графе <tex> G_1 </tex>:<tex> |f'_1| = f'_1(A, значит\overline{A}) \leq c(A, \overline{A}) \leq E </tex>.}} Оценка сложности остальных итераций доказывается аналогично второму случаю. Количество итераций — <tex> O(\log U) </tex>. Значит, общая сложность алгоритма — <tex> O(E^2 \log U) </tex>.