Изменения
Отмена правки 64925, сделанной 93.175.2.31 (обсуждение)
Если увеличивающий путь находить поиском в ширину, то каждую итерацию цикла <tex>\mathrm {while}</tex> можно выполнить за время <tex>O(E)</tex>. Инициализация в процедуре '''Edmonds Karp''' производится за <tex>O(E)</tex>, следовательно время работы алгоритма алгоритма Эдмондса-Карпа составляет <tex>O(V E^2)</tex>.
== Пример графа , на котором алгоритм дает плохую асимптотику ==
[[Файл:MaxFlowWorstCase.png|365px|thumb|right|«Грибок». Схема построения "сложного" для алгоритма Эдмондса-Карпа графа]]
Возьмем <tex>p</tex> равным <tex>k - 1</tex>. В этом случае <tex>n = 6 \cdot k - 2</tex> и <tex>a = k^3</tex>. Заде приводит более хитрые примеры с такой же асимптотикой, но они зависят от выбора пути.
[[Файл:InGraph.png|600px300px|thumb|left| Изначальный граф, нулевой поток]][[Файл:SecondStage.png|600px300px|center|thumb| Граф после <tex>k^2</tex> поисков пути(в нашем случае <tex>k^2 = 4</tex>).<br/>Рёбра из между множествами <tex>S</tex> и <tex>T</tex> полностью насыщены. Поток равен четырем]][[Файл:ThirdStageEdmunds karp.png|600px300px|thumb|left| Алгоритм нашел путь через рёбра бесконечной вместимости, совершив еще <tex>k^2 = 4</tex> шагов. Поток равен восьми]] == См. также ==*[[Определение сети, потока]]*[[Обход в ширину]]*[[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину|Алгоритм Форда-Фалкерсона]]
==Примечания==
