Алгоритм Джонсона — различия между версиями
(Новая страница: «'''Алгоритм Джонсона''' находит кратчайшие пути между всеми парами вершин в ориентированно…») |
(→Сложность) |
||
| Строка 10: | Строка 10: | ||
== Сложность == | == Сложность == | ||
| + | Алгоритм Джонсона работает за <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>. | ||
== См. также == | == См. также == | ||
== Литература == | == Литература == | ||
Версия 21:30, 18 ноября 2010
Алгоритм Джонсона находит кратчайшие пути между всеми парами вершин в ориентированном графе с положительными или отрицательными ребрами, но без отрицательных циклов.
Содержание
Алгоритм
Сохранение кратчайших путей
Изменение веса
Псевдокод
Сложность
Алгоритм Джонсона работает за , где - время работы алгоритма Дейкстры. Если в алгоритме Дейкстры неубывающая очередь с приоритетами реализована в виде фибоначчиевой кучи, то время работы алгоритма Джонсона равно .
