Изменения

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

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

82 байта добавлено, 02:30, 24 декабря 2011
Оценка быстродействия
}}
Если увеличивающий путь находить поиском в ширину, то каждую итерацию цикла '''while''' можно выполнить за время <tex>O(E)</tex>. Инициализация в процедуре '''Edmonds_Karp''' производиться за <tex>O(E)</tex>, следовательно время работы алгоритма алгоритма Эдмондса-Карпа составляет <tex>O(V E^2)</tex>. Заметим также, что сущетсвует сеть [http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlowRevisited "грибок" ] на которое нижняя граница времени работы алгоритмы Эдмондса-Карпа также составляет <tex>\Omega(V E^2)</tex>.
== Литература ==
Анонимный участник

Навигация