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

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

Алгоритм

Дан граф ${\displaystyle G=(V,E)}$ с весовой функцией ${\displaystyle \omega \colon E\to R}$. Если веса всех рёбер ${\displaystyle \omega }$ в графе неотрицательные, можно найти кратчайшие пути между всеми парами вершин, запустив алгоритм Дейкстры один раз для каждой вершины. Если в графе содержатся рёбра с отрицательным весом, но отсутствуют циклы с отрицательным весом, можно вычислить новое множество рёбер с неотрицательными весами, позволяющее воспользоваться предыдущим методом. Новое множество, состоящее из весов рёбер ${\displaystyle {\hat {\omega }}}$, должно удовлетворять следующим свойствам.

• Для всех рёбер ${\displaystyle (u,\;v)}$ новый вес ${\displaystyle {\hat {\omega }}(u,\;v)>0}$.
• Для всех пар вершин ${\displaystyle u,\;v\in V}$ путь ${\displaystyle p}$ является кратчайшим путём из вершины ${\displaystyle u}$ в вершину ${\displaystyle v}$ с использованием весовой функции ${\displaystyle \omega }$ тогда и только тогда, когда ${\displaystyle p}$ — также кратчайший путь из вершины ${\displaystyle u}$ в вершину ${\displaystyle v}$ с весовой функцией ${\displaystyle {\hat {\omega }}}$.

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

Лемма (Изменение весов сохраняет кратчайшие пути). Пусть дан взвешенный ориентированный граф ${\displaystyle G=(V,\;E)}$ с весовой функцией ${\displaystyle \omega \colon E\to R}$, и пусть ${\displaystyle h\colon V\to R}$ — произвольная функция, отображающая вершины на действительные числа. Для каждого ребра ${\displaystyle (u,\;v)\in E}$ определим

${\displaystyle {\hat {\omega }}(u,\;v)=\omega (u,\;v)+h(u)-h(v).}$

Пусть ${\displaystyle p=\langle v_{0},\;v_{1},\;\ldots ,\;v_{k}\rangle }$ — произвольный путь из вершины ${\displaystyle v_{0}}$ в вершину ${\displaystyle v_{k}}$. ${\displaystyle p}$ является кратчайшим путём с весовой функцией ${\displaystyle \omega }$ тогда и только тогда, когда он является кратчайшим путём с весовой функцией ${\displaystyle {\hat {\omega }}}$, то есть равенство ${\displaystyle \omega (p)=\delta (v_{0},\;v_{k})}$ равносильно равенству ${\displaystyle {\hat {\omega }}(p)={\hat {\delta }}(v_{0},\;v_{k})}$. Кроме того, граф ${\displaystyle G}$ содержит цикл с отрицательным весом с использованием весовой функции ${\displaystyle \omega }$ тогда и только тогда, когда он содержит цикл с отрицательным весом с использованием весовой функции ${\displaystyle {\hat {\omega }}}$.

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

1. Для данного графа создадим новый граф ${\displaystyle G'=(V',\;E')}$, где ${\displaystyle V'=V\cup \{s\}}$, для некоторой новой вершины ${\displaystyle s\not \in V}$, а ${\displaystyle E'=E\cup \{(s,\;v):v\in V\}}$.
2. Расширим весовую функцию ${\displaystyle \omega }$ таким образом, чтобы для всех вершин ${\displaystyle v\in V}$ выполнялось равенство ${\displaystyle \omega (s,\;v)=0}$.
3. Далее определим для всех вершин ${\displaystyle v\in V'}$ величину ${\displaystyle h(v)=\delta (s,\;v)}$ и новые веса для всех рёбер ${\displaystyle {\hat {\omega }}(u,\;v)=\omega (u,\;v)+h(u)-h(v)\geqslant 0}$.

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

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

Алгоритм Джонсона
Строится граф ${\displaystyle G'}$
if Bellman_Ford${\displaystyle (G',\;\omega ,\;s)}$ = FALSE
   then do print «Входной граф содержит цикл с отрицательным весом»
           return ø
for для каждой ${\displaystyle v\in V'}$
   do присвоить величине ${\displaystyle h(v)}$ значение ${\displaystyle \delta (s,\;v)}$,
      вычисленное алгоритмом Беллмана — Форда
   for для каждого ребра ${\displaystyle (u,\;v)\in E'}$
      do ${\displaystyle {\hat {\omega }}(u,\;v)\leftarrow \omega (u,\;v)+h(u)-h(v)}$
   for для каждой вершины ${\displaystyle u\in V}$
      do вычисление с помощью алгоритма Дейкстры
         ${\displaystyle (G,\;{\hat {\omega }},\;u)}$ величин ${\displaystyle {\hat {\delta }}(u,\;v)}$
         для всех вершин ${\displaystyle v\in V}$
      for для каждой вершины ${\displaystyle v\in V}$
         do ${\displaystyle d_{uv}\leftarrow {\hat {\delta }}(u,\;v)+h(v)-h(u)}$
return D

Сложность

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

См. также

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

Ссылки

• Визуализатор алгоритма

Литература

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

Эта страница в последний раз была отредактирована 20 марта 2024 в 16:59.