205
правок
Изменения
→Сложность
== Сложность ==
Алгоритм Джонсона работает за <tex>O(VE + VD)</tex>, где <tex>O(D)</tex> - время работы [[Алгоритм Дейктсры| алгоритма Дейкстры]]. Если в алгоритме Дейкстры неубывающая очередь с приоритетами реализована в виде [http://ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8%D0%B5%D0%B2%D0%B0_%D0%BA%D1%83%D1%87%D0%B0| фибоначчиевой кучи], то время работы алгоритма Джонсона равно <math>O(V^2\log V + V E)</math>.
== См. также ==
== Литература ==
