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

Алгоритм Джонсона — позволяет найти кратчайшие пути между всеми парами вершин взвешенного ориентированного графа. Данный алгоритм работает, если в графе содержатся рёбра с положительным или отрицательным весом, но отсутствуют циклы с отрицательным весом. Назван в честь Д. Б. Джонсона^[англ.], опубликовавшего алгоритм в 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 }}$ .

Изменение веса править

Для данного графа создадим новый граф $G'=(V',\;E')$ , где $V'=V\cup \{s\}$ , для некоторой новой вершины $s\not \in V$ , а $E'=E\cup \{(s,\;v):v\in V\}$ .
Расширим весовую функцию $\omega$ таким образом, чтобы для всех вершин $v\in V$ выполнялось равенство $\omega (s,\;v)=0$ .
Далее определим для всех вершин $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.