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

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

Алгоритм

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

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

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

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

\hat{ω} (u, v) = ω (u, v) + h (u) - h (v) .

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

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

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

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

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

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

Сложность

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

См. также

Ссылки

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

Литература

Шаблон:Алгоритмы поиска на графах

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

Содержание