Алгоритм Джонсона

Алгоритм Джонсона находит кратчайшие пути между всеми парами вершин взвешенного ориентированного графа с положительными или отрицательными ребрами, но без отрицательных циклов.

Алгоритм

Псевдокод

В алгоритме Джонсона используется алгоритм Беллмана — Форда и алгоритм Дейкстры. Алгоритм возврашает обычную матрицу [math]D = d_{ij}[/math] размером [math]|V|\times |V|[/math], где [math]d_{ij} = \delta(i,j)[/math], или выдает сообщение о том, что входной граф содержит цикл с отрицательным весом.

Сложность

Алгоритм Джонсона работает за [math]O(VE + VD)[/math], где [math]O(D)[/math] - время работы алгоритма Дейкстры. Если в алгоритме Дейкстры неубывающая очередь с приоритетами реализована в виде фибоначчиевой кучи, то время работы алгоритма Джонсона равно [math]O(V^2\log V + V E)[/math].

См. также

• Алгоритм Дейкстры
• Алгоритм Беллмана — Форда
• Алгоритм Флойда — Уоршелла
• Визуализатор алгоритма

Литература

• Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ.[1] — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.