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

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

Алгоритм

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

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

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

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

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

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

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

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

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

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

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

Сложность

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

См. также

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

Ссылки

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

Литература

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