Изменения

Если увеличивающий путь находить поиском в ширину, то каждую итерацию цикла <tex>\mathrm {while}</tex> можно выполнить за время <tex>O(E)</tex>. Инициализация в процедуре '''Edmonds_KarpEdmonds 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>.

== Пример графа на котором алгоритм дает плохую асимптотику ==[[Файл:MaxFlowWorstCase.png|365px|thumb|right| "грибок"]]Рассмотрим этот случай более подробно. Норман Заде(англ. Norman Zadeh) описал примеры, которые позволяют добиться асимптотики <tex>O\Omega(V^3)</tex><ref>Norman Zadeh. Theoretical Efficiency of the Edmonds-Karp Algorithm for Computing Maximal Flows.</ref>. В нашем примере алгоритм выполнит <tex>O\Omega(V^3)</tex> улучшений пути вне зависимости от выбора этого пути.Разделим все вершины(за исключением <tex>s</tex> и <tex>t</tex> на подмножества: <tex>S</tex>={s1,…\ldots,sk}, </tex>T, </tex>T={t1,…\ldots,tk}, </tex>U, </tex>U={u1,…\ldots,u2p} и </tex>Vи </tex>V={v1,…\ldots,v2p}</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</tex>, <tex>u1</tex>, <tex>u2</tex>, <tex>T</tex>, <tex>S</tex>, <tex>v2</tex>, <tex>v1, t)</tex>, длины <tex>t7</tex>) длины 7, затем путь <tex>(s, u1, u2, u3, u4, S, T, v4, v3, v2, v1, 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>