Изменения

Перейти к: навигация, поиск

Алгоритм Эдмондса-Карпа

1 байт убрано, 12:23, 5 декабря 2015
Оценка быстродействия
}}
Если увеличивающий путь находить поиском в ширину, то каждую итерацию цикла '''while''' можно выполнить за время <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>.
==Примечания==
Анонимный участник

Навигация