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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Алгоритм[править | править исходный текст]

Дан граф 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), но для разреженных графов эта величина в асимптотическом пределе ведёт себя лучше, чем время работы алгоритма Флойда — Уоршелла.

См. также[править | править исходный текст]

Ссылки[править | править исходный текст]

Литература[править | править исходный текст]