147
правок
Изменения
м
→Время работы
Очевидно, что просмотров ребер суммарно <tex>O(E)</tex>, как и в алгоритме Диница. Переход к следующему ребру происходит в следующих случаях:
# просматриваемое Просматриваемое ребро насыщено.# дерево Дерево разрезается по нулевому ребру.# ребро Ребро не лежит в сети кратчайших путей.
На каждый просмотр тратится не <tex>O(1)</tex> а <tex>O(\log(V))</tex>, потому что перед тем, как посмотреть на следующее ребро делается запрос. Значит время работы этой части {{---}} <tex>O(E \log(V))</tex>.
Тогда имеем ассимптотику <tex>O(E\log(V) + V \log(V)) = O((V + E) \log(V))</tex>. И, суммарно, если подставить в алгоритм Диница будем иметь ассимптотику <tex>O(VE \log(V)) </tex>
== Смотри также ==
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину|Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
