Русская Википедия:Алгоритм Джонсона
Алгоритм Джонсона — позволяет найти кратчайшие пути между всеми парами вершин взвешенного ориентированного графа. Данный алгоритм работает, если в графе содержатся рёбра с положительным или отрицательным весом, но отсутствуют циклы с отрицательным весом. Назван в честь Шаблон:Нп5, опубликовавшего алгоритм в 1977 году.
Алгоритм
Дан граф <math>G = (V,E)</math> с весовой функцией <math>\omega\colon E \to R</math>. Если веса всех рёбер <math>\omega</math> в графе неотрицательные, можно найти кратчайшие пути между всеми парами вершин, запустив алгоритм Дейкстры один раз для каждой вершины. Если в графе содержатся рёбра с отрицательным весом, но отсутствуют циклы с отрицательным весом, можно вычислить новое множество рёбер с неотрицательными весами, позволяющее воспользоваться предыдущим методом. Новое множество, состоящее из весов рёбер <math>\hat{\omega}</math>, должно удовлетворять следующим свойствам.
- Для всех рёбер <math>(u,\;v)</math> новый вес <math>\hat{\omega}(u,\;v)>0</math>.
- Для всех пар вершин <math>u,\;v \in V</math> путь <math>p</math> является кратчайшим путём из вершины <math>u</math> в вершину <math>v</math> с использованием весовой функции <math>\omega</math> тогда и только тогда, когда <math>p</math> — также кратчайший путь из вершины <math>u</math> в вершину <math>v</math> с весовой функцией <math>\hat{\omega}</math>.
Сохранение кратчайших путей
Лемма (Изменение весов сохраняет кратчайшие пути). Пусть дан взвешенный ориентированный граф <math>G = (V,\;E)</math> с весовой функцией <math>\omega\colon E \to R</math>, и пусть <math>h\colon V \to R</math> — произвольная функция, отображающая вершины на действительные числа. Для каждого ребра <math>(u,\;v) \in E</math> определим
- <math>\hat{\omega}(u,\;v) = \omega(u,\;v) + h(u) - h(v).</math>
Пусть <math>p = \langle v_0,\;v_1,\;\ldots,\;v_k \rangle</math> — произвольный путь из вершины <math>v_0</math> в вершину <math>v_k</math>. <math>p</math> является кратчайшим путём с весовой функцией <math>\omega</math> тогда и только тогда, когда он является кратчайшим путём с весовой функцией <math>\hat{\omega}</math>, то есть равенство <math>\omega(p) = \delta(v_0,\;v_k)</math> равносильно равенству <math>\hat{\omega}(p) = \hat{\delta}(v_0,\;v_k)</math>. Кроме того, граф <math>G</math> содержит цикл с отрицательным весом с использованием весовой функции <math>\omega</math> тогда и только тогда, когда он содержит цикл с отрицательным весом с использованием весовой функции <math>\hat{\omega}</math>.
Изменение веса
- Для данного графа создадим новый граф <math>G' = (V',\;E')</math>, где <math>V' = V \cup \{s\}</math>, для некоторой новой вершины <math>s \not\in V</math>, а <math>E' = E \cup \{(s,\;v): v \in V\}</math>.
- Расширим весовую функцию <math>\omega</math> таким образом, чтобы для всех вершин <math>v \in V</math> выполнялось равенство <math>\omega(s,\;v) = 0</math>.
- Далее определим для всех вершин <math>v \in V'</math> величину <math>h(v) = \delta(s,\;v)</math> и новые веса для всех рёбер <math>\hat{\omega}(u,\;v) = \omega(u,\;v) + h(u) - h(v) \geqslant 0</math>.
Основная процедура
В алгоритме Джонсона используется алгоритм Беллмана — Форда и алгоритм Дейкстры, реализованные в виде подпрограмм. Рёбра хранятся в виде списков смежных вершин. Алгоритм возвращает обычную матрицу <math>D = d_{ij}</math> размером <math>|V|\times |V|</math>, где <math>d_{ij} = \delta(i,\;j)</math>, или выдает сообщение о том, что входной граф содержит цикл с отрицательным весом.
Алгоритм Джонсона
Строится граф <math>G'</math>
if Bellman_Ford<math>(G',\;\omega,\;s)</math> = FALSE
then do print «Входной граф содержит цикл с отрицательным весом»
return ø
for для каждой <math>v \in V'</math>
do присвоить величине <math>h(v)</math> значение <math>\delta(s,\;v)</math>,
вычисленное алгоритмом Беллмана — Форда
for для каждого ребра <math>(u,\;v) \in E'</math>
do <math>\hat{\omega}(u,\;v) \leftarrow \omega(u,\;v) + h(u) - h(v)</math>
for для каждой вершины <math>u \in V</math>
do вычисление с помощью алгоритма Дейкстры
<math>(G,\;\hat{\omega},\;u)</math> величин <math>\hat{\delta}(u,\;v)</math>
для всех вершин <math>v \in V</math>
for для каждой вершины <math>v \in V</math>
do <math>d_{uv} \leftarrow \hat{\delta}(u,\;v) + h(v) - h(u)</math>
return D
Сложность
Если в алгоритме Дейкстры неубывающая очередь с приоритетами реализована в виде фибоначчиевой кучи, то время работы алгоритма Джонсона равно <math>O(V^2\log V + V E)</math>. При более простой реализации неубывающей очереди с приоритетами время работы становится равным <math>O(V E\log V)</math>, но для разреженных графов эта величина в асимптотическом пределе ведёт себя лучше, чем время работы алгоритма Флойда — Уоршелла.
См. также
Ссылки
Литература
Шаблон:Алгоритмы поиска на графах
