Изменения

Перейти к: навигация, поиск
Асимптотика
===Асимптотика===
Если информация о входящих и исходящих дугах будет храниться в виде связных списков, то для того, чтобы пропустить поток, на каждой итерации будет выполнено <tex>O(K + E_i)</tex> действий, где <tex>K</tex> соответствует числу рёбер, для которых остаточная пропускная способность уменьшилась, но осталась положительной, а <tex>E_i</tex> — числу удалённых ребер. Таким образом, для поиска блокирующего потока будет выполнено <tex>\sum\limits_i{O(K+E_i)} = O(K^2)</tex> действий.
 
<b>Замечание</b> Алгоритм Малхотры — Кумара — Махешвари для поиска блокирующего потока использует алгоритм узкого места.
==Источники==
Анонимный участник

Навигация