Изменения

Если увеличивающий путь находить поиском в ширину, то каждую итерацию цикла <tex>\mathrm {while}</tex> можно выполнить за время <tex>O(E)</tex>. Инициализация в процедуре '''Edmonds Karp''' производится за <tex>O(E)</tex>, следовательно время работы алгоритма алгоритма Эдмондса-Карпа составляет <tex>O(V E^2)</tex>. Заметим также, что сущетсвует '''сеть "грибок"'''<ref>[https://www.topcoder.com/community/data-science/data-science-tutorials/maximum-flow-augmenting-path-algorithms-comparison/#! Cтатья на TopCoder.com ]</ref> на которой нижняя граница времени работы алгоритмы Эдмондса-Карпа также составляет <tex>\Omega(V E^2)</tex>.

Заметим также, что сущетсвует ''сеть "грибок"''<ref>[https://www.topcoder.com/community/data-science/data-science-tutorials/maximum-flow-augmenting-path-algorithms-comparison/#! Cтатья на TopCoder.com ]</ref> на которой нижняя граница времени работы алгоритмы Эдмондса-Карпа также составляет <tex>\Omega(V E^2)</tex>.Рассмотрим этот случай более подробно. Норман Заде(англ. Norman Zadeh) описал примеры, которые позволяют добиться асимптотики <tex>\Omega(V^3)</tex><ref>Norman Zadeh. Theoretical Efficiency of the Edmonds-Karp Algorithm for Computing Maximal Flows.</ref>. В нашем примере алгоритм выполнит <tex>\Omega(V^3)</tex> улучшений пути вне зависимости от выбора этого пути.Разделим все вершины (за исключением <tex>s</tex> и <tex>t</tex> на подмножества: *<tex>S={s1s_1,\ldots,sks_k}</tex>— множество вершин, в которые входят ребра из <tex>s</tex> с пропускной способностью k, *<tex>T={t1t_1,\ldots,tkt_k}</tex>— множество вершин, из которых исходят ребра в <tex>t</tex> с пропускной способностью k, *<tex>U={u1u_1,\ldots,u2pu_{2p}}</tex> и — множество вершин, достижимых из <tex>s</tex> по ребрам с бесконечной пропускной способностью(не используя иные ребра),*<tex>V={v1v_1,\ldots,v2pv_{2p}}</tex>— множество вершин, из которых можно достигнуть <tex>t</tex> по ребрам с бесконечной пропускной способностью(не используя иные ребра).  <tex>S</tex> и <tex>T</tex> содержат <tex>k</tex> вершин, <tex>U</tex> и <tex>V</tex> содержат <tex>2p</tex> вершин. Где <tex>k</tex> и <tex>p</tex> фиксированные целые числа. Каждое ребро, выделенное жирным(см. рисунок, соединяют множества <tex>S</tex> и <tex>T</tex>), имеет единичную пропускную способность; пунктирные ребра имеют бесконечную пропускную способность; остальные ребра(в форме дуги) имеют пропускную способность <tex>k</tex>.В начале работы алгоритма путь увеличиться <tex>k^2</tex> раз по пути (<tex>s</tex>, <tex>S</tex>, <tex>T</tex>, <tex>t</tex>), длина которого равна трем. После этого остаточная сеть будет содержать обратные ребра из <tex>T</tex> в <tex>S</tex>, и алгоритм выберет еще <tex>k^2</tex> путей <tex>(s, u1u_1, u2u_2, T, S, v2v_2, v1v_1, t)</tex> длины <tex>7</tex>, затем путь <tex>(s, u1u_1, u2u_2, u3u_3, u4u_4, S, T, v4v_4, v3v_3, v2v_2, v1v_1, t)</tex> длины <tex>11</tex> и так далее...:Число вершин в нашей сети: <tex>n = 2\cdot k + 4\cdot p + 2</tex>. :Число ребер: <tex> m = k^2 + 2\cdot p\cdot k + 2\cdot k + 4\cdot p</tex>.  Нетрудно заметить, что число удлиняющих путей <tex> a = k^2\cdot (p+1)</tex>.Возьмем <tex>p</tex> равным <tex>k - 1</tex>. В этом случае <tex>n = 6 \cdot k - 2</tex> и <tex>a = k^3</tex>. Заде приводит более хитрые примеры с такой же асимптотикой, но они зависят от выбора пути.