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

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

Алгоритм

Описание

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

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

Пусть — произвольное отображение из множества вершин в вещественные числа. Тогда новой весовой функцией будет .

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

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

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

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

Лемма:

Пусть — два пути и Тогда

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

Рассмотрим путь

Его вес с новой весовой функцией равен .

Вставим определение функции

Заметим, что потенциалы все промежуточных вершин в пути сократятся.

По изначальному предположению: . С новой весовой функцией веса соответствующих путей будут:

Отсюда,

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

Теорема:

В графе нет отрицательных циклов существует потенциальная функция

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

[math]\Leftarrow [/math]: Рассмотрим произвольный [math]C[/math] — цикл в графе [math]G[/math]

По лемме, его вес равен

[math]\Rightarrow [/math]: Добавим фиктивную вершину [math]s[/math] в граф, а также ребра [math] s \to u [/math] весом [math] 0 [/math] для всех [math] u [/math].

Обозначим как минимальное расстояние между вершинами , введем потенциальную функцию

Рассмотрим вес произвольного ребра : .

Поскольку — вес какого-то пути , а — вес кратчайшего пути , то .

Псевдокод

Предварительно построим граф [math]G' = (V',\;E')[/math], где [math]V' = V \cup \{s\}[/math], [math]s \not\in V[/math], а

function Johnson(G): int[][]
    if BellmanFord[math](G',\;\omega,\;s)[/math] == false
        print "Входной граф содержит цикл с отрицательным весом"
        return [math]\varnothing[/math]
    else for [math]v \in V'[/math]
        [math]\varphi(v)[/math] = [math]\delta(s,\;v)[/math] // [math]\delta(s,\;v)[/math] вычислено алгоритмом Беллмана — Форда
        for [math](u,\;v) \in E'[/math]
            [math]\omega_\varphi(u,\;v)[/math] = [math] \omega(u,\;v) + \varphi(u) - \varphi(v)[/math]
        for [math]u \in V[/math]
            Dijkstra[math](G,\;\omega_\varphi,\;u)[/math]
            for [math]v \in V[/math]
                [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]. В случае реализации очереди с приоритетами в виде двоичной кучи время работы равно [math]O(V E \log V)[/math].

См. также

Источники информации

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

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