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

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

Дан граф G = (V,E) с весовой функцией . Если веса всех рёбер ω в графе неотрицательные, можно найти кратчайшие пути между всеми парами вершин, запустив алгоритм Дейкстры один раз для каждой вершины. Если в графе содержатся рёбра с отрицательным весом, но отсутствуют циклы с отрицательным весом, можно вычислить новое множество рёбер с неотрицательными весами, позволяющее воспользоваться предыдущим методом. Новое множество, состоящее из весов рёбер , должно удовлетворять следующим свойствам.

• Для всех рёбер  новый вес .

• Для всех пар вершин  путь p является кратчайшим путем из вершины u в вершину v с использованием весовой функции ω тогда и только тогда, когда p — также кратчайший путь из вершины u в вершину v с весовой функцией . 

Лемма (Изменение весов сохраняет кратчайшие пути). Пусть дан взвешенный ориентированный граф  с весовой функцией , и пусть  — произвольная функция, отображающая вершины на действительные числа. Для каждого ребра  определим

Пусть  — произвольный путь из вершины v0 в вершину vk. p является кратчайшим путем с весовой функцией ω тогда и только тогда, когда он является кратчайшим путем с весовой функцией , то есть равенство  равносильно равенству . Кроме того, граф G содержит цикл с отрицательным весом с использованием весовой функции ω тогда и только тогда, когда он содержит цикл с отрицательным весом с использованием весовой функции .

Изменение веса:

1. Для данного графа создадим новый граф , где , для некоторой новой вершины , а .

2. Расширим весовую функцию ω таким образом, чтобы для всех вершин  выполнялось равенство .

3. Далее определим для всех вершин  величину  и новые веса для всех рёбер . 

В А.Д. используется алгоритм Беллмана — Форда и алгоритм Дейкстры, реализованные в виде подпрограмм. Рёбра хранятся в виде списков смежных вершин. Алгоритм возврашает обычную матрицу D = dij размером , где , или выдает сообщение о том, что входной граф содержит цикл с отрицательным весом.

Строится граф G'

if Bellman_Ford = FALSE

then print «Входной граф содержит цикл с отрицательным весом»

else for для каждой

do присвоить величине h(v) значение ,

вычисленное алгоритмом Беллмана — Форда

for для каждого ребра

do

for для каждой вершины

do вычисление с помощью алгоритма Дейкстры

величин

для всех вершин

for для каждой вершины

do

return D

Если в алгоритме Дейкстры неубывающая очередь с приоритетами реализована в виде фибоначчиевой кучи, то время работы алгоритма Джонсона равно O(V2log V + VE). При более простой реализации неубывающей очереди с приоритетами время работы становится равным O(VElog V), но для разреженных графов эта величина в асимптотическом пределе ведёт себя лучше, чем время работы алгоритма Флойда — Уоршелла.

Лит.: Томас Х. Кормен и др. Алгоритмы: построение и анализ — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296. — ISBN 5-8459-0857-4.