Алгоритм Джонсона (Glikjnmb :'kuvkug)

Перейти к навигации Перейти к поиску

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

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

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

Сохранение кратчайших путей

[править | править код]

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

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

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

[править | править код]
  1. Для данного графа создадим новый граф , где , для некоторой новой вершины , а .
  2. Расширим весовую функцию таким образом, чтобы для всех вершин выполнялось равенство .
  3. Далее определим для всех вершин величину и новые веса для всех рёбер .

Основная процедура

[править | править код]

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

Алгоритм Джонсона
Строится граф 
if Bellman_Ford = FALSE
   then do print «Входной граф содержит цикл с отрицательным весом»
           return ø
for для каждой 
   do присвоить величине  значение ,
      вычисленное алгоритмом Беллмана — Форда
   for для каждого ребра 
      do 
   for для каждой вершины 
      do вычисление с помощью алгоритма Дейкстры
          величин 
         для всех вершин 
      for для каждой вершины 
         do 
return D

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

Литература

[править | править код]
  • Томас Х. Кормен и др. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 726. — ISBN 5-8459-0857-4.
  • Томас Х. Кормен и др. Алгоритмы: построение и анализ. — 1-е изд. — М.: МЦНМО, 2004. — С. 523. — ISBN 5-900916-37-5.