Алгоритм Джонсона
Алгоритм Джонсона находит кратчайшие пути между всеми парами вершин взвешенного ориентированного графа с положительными или отрицательными ребрами, но без отрицательных циклов.
Содержание
Алгоритм
Сохранение кратчайших путей
Изменение веса
Псевдокод
В алгоритме Джонсона используется алгоритм Беллмана — Форда и алгоритм Дейкстры. Алгоритм возврашает обычную матрицу размером , где , или выдает сообщение о том, что входной граф содержит цикл с отрицательным весом.
Алгоритм Джонсона
Строится графif Bellman_Ford == FALSE then out << «Входной граф содержит цикл с отрицательным весом» else for для каждой do присвоить величине значение , вычисленное алгоритмом Беллмана — Форда for для каждого ребра do for для каждой вершины do вычисление с помощью алгоритма Дейкстры величин для всех вершин for для каждой вершины do return D
Сложность
Алгоритм Джонсона работает за алгоритма Дейкстры. Если в алгоритме Дейкстры неубывающая очередь с приоритетами реализована в виде фибоначчиевой кучи, то время работы алгоритма Джонсона равно .
, где - время работыСм. также
Литература
- Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ.[1] — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.