Изменения

dfs()

<tex>p \leftarrow [s]</tex> //путь <tex>p</tex>

<tex>v \leftarrow s</tex>; //текущая вершина и указатель на вершину первого неудалённого ребра

завершить алгоритм;

else

удалить <tex>(uv)</tex> из <tex>V(G)</tex>; //<tex>uv</tex> - последнее ребро на пути <tex>p</tex>

удалить <tex>v</tex> из <tex>p</tex>;

do

//<tex>w</tex> - вершина смежная с <tex>v</tex>

<tex>p \leftarrow p+[w]</tex>;

<tex>v \leftarrow w;</tex>

while(<tex>w \ne t</tex>);

удалить <tex>(vw)</tex> из <tex>V(G);</tex>

dfs();

Если обход в глубину достигает стока, насыщается как минимум одно ребро, иначе как минимум один указатель продвигается вперед. Значит один запуск обхода в глубину работает за <tex>O(V + K)</tex>, где <tex>V</tex> — число вершин в графе, а <tex>K</tex> — число продвижения указателей. Ввиду того, что всего запусков обхода в глубину в рамках поиска одного [[Блокирующий поток|блокирующего потока]] будет <tex>O(P)</tex>, где <tex>P</tex> — число рёбер, насыщенных этим блокирующим потоком, то весь алгоритм поиска блокирующего потока отработает за <tex>O(PV + \sum\limits_i{K_i})</tex>, что, учитывая, что все указатели в сумме прошли расстояние <tex>O(E)</tex>, дает асимптотику <tex>O(PV + E)</tex>. В худшем случае, когда блокирующий поток насыщает все ребра, асимптотика получается <tex>O(VE)</tex>.