Изменения
Отмена правки 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> шагов. Поток равен восьми]] == См. также ==*[[Определение сети, потока]]*[[Обход в ширину]]*[[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину|Алгоритм Форда-Фалкерсона]]
==Примечания==
== Источники информации ==
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
*[https://ru.wikipedia.org/wiki/Алгоритм_Эдмондса_—_Карпа Википедия: Алоритм Алгоритм Эдмондса-Карпа]* [https://en.wikipedia.org/wiki/Edmonds–Karp_algorithm Википедия: Алоритм Алгоритм Эдмондса-Карпа (англ.)]
*[https://www.topcoder.com/community/data-science/data-science-tutorials/maximum-flow-augmenting-path-algorithms-comparison/#! Статья на TopCoder.com]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о максимальном потоке]]
