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

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

Алгоритм

Описание

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

В этом алгоритме используется метод изменения веса (англ. reweighting). Суть его заключается в том, что для заданного графа $G$ строится новая весовая функция $\hat{\omega}$, неотрицательная для всех ребер графа $G$ и сохраняющая кратчайшие пути. Такая весовая функция строится при помощи так называемой потенциальной функции.

Определение:

Пусть $\varphi : V \rightarrow \mathbb R$ - произвольное отображение из множества вершин в вещественные числа. Тогда новой весовой функцией будет $\omega_\varphi(u, v) = \omega(u, v) + \varphi(u) - \varphi(v)$.

Такая потенциальная функция строится при помощи добавлении фиктивной вершины в $G$ и запуском алгоритма Форда-Беллмана из нее. На этом же этапе мы сможем обнаружить наличие отрицательного цикла в графе.

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

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

Утверждается, что если какой-то путь $P$ был кратчайшим относительно весовой функции $\omega$, то он будет кратчайшим и относительно новой весовой функции $\hat{\omega}$.

Лемма:

Пусть $P,\; Q : a \rightsquigarrow b\;$ и $w(P) \lt w(Q).$ Тогда $\forall \varphi: \; w_\varphi(P) \lt w_\varphi(Q)$

Доказательство:

$\triangleright$

$P: \;u_0 \rightarrow u_1 \rightarrow u_2 \rightarrow ... \rightarrow u_k$ $w_\varphi(P) = w_\varphi(u_0u_1) + w_\varphi(u_1u_2) + ... + w_\varphi(u_{k-1}u_k) = \varphi(u_0) + w(u_0u_1) - \varphi(u_1) + ... + \varphi(u_{k-1}) + w(u_{k-1}u_k) - \varphi(u_k) = \varphi(u_0) + w(P) - \varphi(u_k)$ $w(P) \lt w(Q)$ $w_\varphi(P) = \varphi(a) + w(P) - \varphi(b)$ $w_\varphi(Q) = \varphi(a) + w(Q) - \varphi(b)$ Отсюда, $w_\varphi(P) \lt w_\varphi(Q)$

$\triangleleft$

Теорема о существовании потенциальной функции

Теорема:

В графе $G$ нет отрицательных циклов $\Leftrightarrow$ существует потенциальная функция $\phi:\; \forall uv \in E\; w_\varphi(uv) \ge 0$

Доказательство:

$\triangleright$

$\Leftarrow$: $C$ - цикл в графе $G$ $w(C) = w_\varphi(C) - \sum\limits_{uv \in C} (\varphi(u) - \varphi(v))= w_\varphi(C) \ge 0$ $\Rightarrow$: Добавим вершину $s$ в граф, соединим её со всеми вершинами графа $G$ ребрами весом $w = 0$. Обозначение : $\delta(i,\;j)$ - минимальное расстояние между вершинами $i,\; j$ графа $G$. $\phi(u) = \delta(s,\;u)$ $w_\phi(uv) = \phi(u) + w(uv) - \phi(v) = \delta(s,\;u) + w(uv) - \delta(s,\;v)$. $\delta(s,\;u) + w(uv) =$ {какой-то путь $s \rightsquigarrow v$}. $\delta(s,\;v) =$ {минимальный путь $s \rightsquigarrow v$}. Следовательно, $w_\phi(uv) \ge 0$

$\triangleleft$

Псевдокод

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

Строится граф $G' = (V',\;E')$, где $V' = V \cup \{s\}$, 
для некоторой новой вершины $s \not\in V$, а $E' = E \cup \{(s,\;v): \omega(s, v) = 0,\ v \in V \}$
if Bellman_Ford$(G',\;\omega,\;s)$ == FALSE
   then out << «Входной граф содержит цикл с отрицательным весом»
   else for для каждой $v \in V'$
        do присвоить величине $\varphi(v)$ значение $\delta(s,\;v)$,
           вычисленное алгоритмом Беллмана — Форда
        for для каждого ребра $(u,\;v) \in E'$
            do $w_\varphi(u,\;v) \leftarrow w(u,\;v) + \varphi(u) - \varphi(v)$
        for для каждой вершины $u \in V$
            do вычисление с помощью алгоритма Дейкстры
            $(G,\;w_\varphi,\;u)$ величин $\delta_\varphi(u,\;v)$
            для всех вершин $v \in V$
            for для каждой вершины $v \in V$
                do $d_{uv} \leftarrow \delta_\varphi(u,\;v) + \varphi(v) - \varphi(u)$
   return $d$

Итого, в начале алгоритм Форда-Беллмана либо строит потенциальную функцию такую, что после перевзвешивания все веса ребер будут неотрицательны, либо выдает сообщение о том, что в графе присутствует отрицательный цикл.

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

Сложность

Алгоритм Джонсона работает за $O(VE + VD)$, где $O(D)$ - время работы алгоритма Дейкстры. Если в алгоритме Дейкстры неубывающая очередь с приоритетами реализована в виде фибоначчиевой кучи, то время работы алгоритма Джонсона равно $O(V^2\log V + V E)$.

См. также

• Алгоритм Дейкстры
• Алгоритм Форда-Беллмана
• Алгоритм Флойда
• Визуализатор алгоритма

Литература

• Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ.[1] — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.