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

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

Алгоритм

Дан граф $G = (V,E)$ с весовой функцией $\omega: E \rightarrow 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 : E \to R$, и пусть $h : 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 print «Входной граф содержит цикл с отрицательным весом»
   else 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 + V E)$. При более простой реализации неубывающей очереди с приоритетами время работы становится равным $O(V E\log V)$, но для разреженных графов эта величина в асимптотическом пределе ведёт себя лучше, чем время работы алгоритма Флойда — Уоршелла.

См. также

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

Ссылки

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

Литература

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