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

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

Алгоритм

Описание

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

В этом алгоритме используется метод изменения веса (англ. reweighting). Суть его заключается в том, что для заданного графа [math] G [/math] строится новая весовая функция [math] \omega_\varphi [/math], неотрицательная для всех ребер графа [math] G [/math] и сохраняющая кратчайшие пути. Такая весовая функция строится с помощью так называемой потенциальной функции.

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

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

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

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

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

Утверждается, что если какой-то путь [math] P [/math] был кратчайшим относительно весовой функции [math] \omega [/math], то он будет кратчайшим и относительно новой весовой функции [math] \omega_\varphi [/math].

Лемма:

Пусть [math]P,\; Q [/math] — два пути [math] a \rightsquigarrow b\;[/math] и [math]\omega(P) \lt \omega(Q).[/math] Тогда [math]\forall \varphi: \; \omega_\varphi(P) \lt \omega_\varphi(Q)[/math]

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

[math]\triangleright[/math]

Рассмотрим путь [math]P: \;u_0 \rightarrow u_1 \rightarrow u_2 \rightarrow ... \rightarrow u_k [/math] Его вес с новой весовой функцией равен [math]\omega_\varphi(P) = \omega_\varphi(u_0u_1) + \omega_\varphi(u_1u_2) + ... + \omega_\varphi(u_{k-1}u_k) [/math]. Вставим определение функции [math] \omega_\varphi : \omega_\varphi(P) = \varphi(u_0) + \omega(u_0u_1) - \varphi(u_1) + ... + \varphi(u_{k-1}) + \omega(u_{k-1}u_k) - \varphi(u_k) [/math] Заметим, что потенциалы все промежуточных вершин в пути сократятся. [math] \omega_\varphi(P) = \varphi(u_0) + \omega(P) - \varphi(u_k)[/math] По изначальному предположению: [math]\omega(P) \lt \omega(Q)[/math]. С новой весовой функцией веса соответствующих путей будут: [math]\omega_\varphi(P) = \varphi(a) + \omega(P) - \varphi(b)[/math] [math]\omega_\varphi(Q) = \varphi(a) + \omega(Q) - \varphi(b)[/math] Отсюда, [math]\omega_\varphi(P) \lt \omega_\varphi(Q)[/math]

[math]\triangleleft[/math]

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

Теорема:

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

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

[math]\triangleright[/math]

[math]\Leftarrow [/math]: Рассмотрим произвольный [math]C[/math] - цикл в графе [math]G[/math] По лемме, его вес равен [math] \omega(C) = \omega_\varphi(C) - \varphi(u_0) - \varphi(u_0) = \omega_\varphi(C) \ge 0[/math] [math]\Rightarrow [/math]: Добавим фиктивную вершину [math]s[/math] в граф, а также ребра [math] s \to u [/math] весом [math] 0 [/math] для всех [math] u [/math]. Обозначим [math]\delta(u,v)[/math] как минимальное расстояние между вершинами [math]u,\; v[/math]. Введем потенциальную функцию [math] \phi [/math] следующим образом: [math]\phi(u) = \delta(s,u)[/math] Рассмотрим вес произвольного ребра [math] uv \in E [/math]: [math]\omega_\phi(uv) = \phi(u) + \omega(uv) - \phi(v) = \delta(s, u) + \omega(uv) - \delta(s, v)[/math]. Поскольку [math]\delta(s, u) + \omega(uv) [/math] — вес какого-то пути [math] s \rightsquigarrow v [/math], а [math] \delta(s, v) [/math] — вес кратчайшего пути [math] s \rightsquigarrow v[/math], то [math] \delta(s, u) + \omega(uv) \ge \delta(s, v) \Rightarrow \delta(s, u) + w\omega(uv) - \delta(s, v) = \omega_\varphi(uv) \ge 0 [/math].

[math]\triangleleft[/math]

Псевдокод

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

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

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

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

Сложность

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

См. также

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

Литература

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