Алгоритм Джонсона — различия между версиями
(→Сложность) |
(→См. также) |
||
| Строка 13: | Строка 13: | ||
== См. также == | == См. также == | ||
| + | * [[Алгоритм Дейкстры]] | ||
| + | * [[Алгоритм Беллмана — Форда]] | ||
| + | * [[Алгоритм Флойда — Уоршелла]] | ||
| + | * [http://rain.ifmo.ru/cat/view.php/vis/graph-paths/johnson-2001 Визуализатор алгоритма] | ||
== Литература == | == Литература == | ||
Версия 21:33, 18 ноября 2010
Алгоритм Джонсона находит кратчайшие пути между всеми парами вершин в ориентированном графе с положительными или отрицательными ребрами, но без отрицательных циклов.
Содержание
Алгоритм
Сохранение кратчайших путей
Изменение веса
Псевдокод
Сложность
Алгоритм Джонсона работает за , где - время работы алгоритма Дейкстры. Если в алгоритме Дейкстры неубывающая очередь с приоритетами реализована в виде фибоначчиевой кучи, то время работы алгоритма Джонсона равно .
