42
правки
Изменения
→Асимптотика
Обозначим время работы поиска кратчайшего пути <tex>F(V, E)</tex>.
[[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости|Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]] работает за <tex>O(F(V, E) \cdot |f|)</tex>.
Если использовать [[Алгоритм Дейкстры|алгоритм Дейкстры]] с Фиббоначевыми кучами, то <tex>F(V, E)= V log V + E</tex>. В результате получим время работы <tex>O((V log V + E) \cdot |f|+ V E)</tex>.
Это лучше, чем <tex>O((V E) \cdot |f|)</tex>, что получается при использовании [[Алгоритм Форда-Беллмана|алгоритма Форда-Беллмана]].
