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

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

АлгоритмПравить

Дан граф $G=(V,E)$$G=(V,E)$  с весовой функцией $\mathrm{\omega <!--\; \omega \; -->}:<!--\; :\; -->E\to <!--\; \to \; -->R$$\omega \colon E\to R$ . Если веса всех рёбер $\mathrm{\omega <!--\; \omega \; -->}$$\omega$  в графе неотрицательные, можно найти кратчайшие пути между всеми парами вершин, запустив алгоритм Дейкстры один раз для каждой вершины. Если в графе содержатся рёбра с отрицательным весом, но отсутствуют циклы с отрицательным весом, можно вычислить новое множество рёбер с неотрицательными весами, позволяющее воспользоваться предыдущим методом. Новое множество, состоящее из весов рёбер $\stackrel{^<!--\; ^\; -->}{\mathrm{\omega <!--\; \omega \; -->}}$${\hat {\omega }}$ , должно удовлетворять следующим свойствам.

• Для всех рёбер $(u,v)$$(u,\;v)$  новый вес $\stackrel{^<!--\; ^\; -->}{\mathrm{\omega <!--\; \omega \; -->}}(u,v)>0$${\hat {\omega }}(u,\;v)>0$ .
• Для всех пар вершин $u,v\in <!--\; \in \; -->V$$u,\;v\in V$  путь $p$$p$  является кратчайшим путём из вершины $u$$u$  в вершину $v$$v$  с использованием весовой функции $\mathrm{\omega <!--\; \omega \; -->}$$\omega$  тогда и только тогда, когда $p$$p$  — также кратчайший путь из вершины $u$$u$  в вершину $v$$v$  с весовой функцией $\stackrel{^<!--\; ^\; -->}{\mathrm{\omega <!--\; \omega \; -->}}$${\hat {\omega }}$ .

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

Лемма (Изменение весов сохраняет кратчайшие пути). Пусть дан взвешенный ориентированный граф $G=(V,E)$$G=(V,\;E)$  с весовой функцией $\mathrm{\omega <!--\; \omega \; -->}:<!--\; :\; -->E\to <!--\; \to \; -->R$$\omega \colon E\to R$ , и пусть $h:<!--\; :\; -->V\to <!--\; \to \; -->R$$h\colon V\to R$  — произвольная функция, отображающая вершины на действительные числа. Для каждого ребра $(u,v)\in <!--\; \in \; -->E$$(u,\;v)\in E$  определим

$\stackrel{^<!--\; ^\; -->}{\mathrm{\omega <!--\; \omega \; -->}}(u,v)=\mathrm{\omega <!--\; \omega \; -->}(u,v)+h(u)-<!--\; -\; -->h(v).$${\hat {\omega }}(u,\;v)=\omega (u,\;v)+h(u)-h(v).$ 

Пусть $p=⟨<!--\; ⟨\; -->v_0,v_1,\dots <!--\; \dots \; -->,v_k⟩<!--\; ⟩\; -->$$p=\langle v_{0},\;v_{1},\;\ldots ,\;v_{k}\rangle$  — произвольный путь из вершины $v_0$$v_{0}$  в вершину $v_k$$v_{k}$ . $p$$p$  является кратчайшим путём с весовой функцией $\mathrm{\omega <!--\; \omega \; -->}$$\omega$  тогда и только тогда, когда он является кратчайшим путём с весовой функцией $\stackrel{^<!--\; ^\; -->}{\mathrm{\omega <!--\; \omega \; -->}}$${\hat {\omega }}$ , то есть равенство $\mathrm{\omega <!--\; \omega \; -->}(p)=\mathrm{\delta <!--\; \delta \; -->}(v_0,v_k)$$\omega (p)=\delta (v_{0},\;v_{k})$  равносильно равенству $\stackrel{^<!--\; ^\; -->}{\mathrm{\omega <!--\; \omega \; -->}}(p)=\stackrel{^<!--\; ^\; -->}{\mathrm{\delta <!--\; \delta \; -->}}(v_0,v_k)$${\hat {\omega }}(p)={\hat {\delta }}(v_{0},\;v_{k})$ . Кроме того, граф $G$$G$  содержит цикл с отрицательным весом с использованием весовой функции $\mathrm{\omega <!--\; \omega \; -->}$$\omega$  тогда и только тогда, когда он содержит цикл с отрицательным весом с использованием весовой функции $\stackrel{^<!--\; ^\; -->}{\mathrm{\omega <!--\; \omega \; -->}}$${\hat {\omega }}$ .

Изменение весаПравить

1. Для данного графа создадим новый граф $G^{\prime }=(V^{\prime },E^{\prime })$$G'=(V',\;E')$ , где $V^{\prime }=V\cup <!--\; \cup \; -->\{s\}$$V'=V\cup \{s\}$ , для некоторой новой вершины $s\notin V$$s\not \in V$ , а $E^{\prime }=E\cup <!--\; \cup \; -->\{(s,v):v\in <!--\; \in \; -->V\}$$E'=E\cup \{(s,\;v):v\in V\}$ .
2. Расширим весовую функцию $\mathrm{\omega <!--\; \omega \; -->}$$\omega$  таким образом, чтобы для всех вершин $v\in <!--\; \in \; -->V$$v\in V$  выполнялось равенство $\mathrm{\omega <!--\; \omega \; -->}(s,v)=0$$\omega (s,\;v)=0$ .
3. Далее определим для всех вершин $v\in <!--\; \in \; -->V^{\prime }$$v\in V'$  величину $h(v)=\mathrm{\delta <!--\; \delta \; -->}(s,v)$$h(v)=\delta (s,\;v)$  и новые веса для всех рёбер $\stackrel{^<!--\; ^\; -->}{\mathrm{\omega <!--\; \omega \; -->}}(u,v)=\mathrm{\omega <!--\; \omega \; -->}(u,v)+h(u)-<!--\; -\; -->h(v)⩾<!--\; ⩾\; -->0$${\hat {\omega }}(u,\;v)=\omega (u,\;v)+h(u)-h(v)\geqslant 0$ .

Основная процедураПравить

В алгоритме Джонсона используется алгоритм Беллмана — Форда и алгоритм Дейкстры, реализованные в виде подпрограмм. Рёбра хранятся в виде списков смежных вершин. Алгоритм возвращает обычную матрицу $D=d_{ij}$$D=d_{ij}$  размером $|V|\times <!--\; \times \; -->|V|$$|V|\times |V|$ , где $d_{ij}=\mathrm{\delta <!--\; \delta \; -->}(i,j)$$d_{ij}=\delta (i,\;j)$ , или выдает сообщение о том, что входной граф содержит цикл с отрицательным весом.

Алгоритм Джонсона
Строится граф $G^{\prime }$$G'$ 
if Bellman_Ford$(G^{\prime },\mathrm{\omega <!--\; \omega \; -->},s)$$(G',\;\omega ,\;s)$  = FALSE
   then do print «Входной граф содержит цикл с отрицательным весом»
           return ø
for для каждой $v\in <!--\; \in \; -->V^{\prime }$$v\in V'$ 
   do присвоить величине $h(v)$$h(v)$  значение $\mathrm{\delta <!--\; \delta \; -->}(s,v)$$\delta (s,\;v)$ ,
      вычисленное алгоритмом Беллмана — Форда
   for для каждого ребра $(u,v)\in <!--\; \in \; -->E^{\prime }$$(u,\;v)\in E'$ 
      do $\stackrel{^<!--\; ^\; -->}{\mathrm{\omega <!--\; \omega \; -->}}(u,v)\leftarrow <!--\; \leftarrow \; -->\mathrm{\omega <!--\; \omega \; -->}(u,v)+h(u)-<!--\; -\; -->h(v)$${\hat {\omega }}(u,\;v)\leftarrow \omega (u,\;v)+h(u)-h(v)$ 
   for для каждой вершины $u\in <!--\; \in \; -->V$$u\in V$ 
      do вычисление с помощью алгоритма Дейкстры
         $(G,\stackrel{^<!--\; ^\; -->}{\mathrm{\omega <!--\; \omega \; -->}},u)$$(G,\;{\hat {\omega }},\;u)$  величин $\stackrel{^<!--\; ^\; -->}{\mathrm{\delta <!--\; \delta \; -->}}(u,v)$${\hat {\delta }}(u,\;v)$ 
         для всех вершин $v\in <!--\; \in \; -->V$$v\in V$ 
      for для каждой вершины $v\in <!--\; \in \; -->V$$v\in V$ 
         do $d_{uv}\leftarrow <!--\; \leftarrow \; -->\stackrel{^<!--\; ^\; -->}{\mathrm{\delta <!--\; \delta \; -->}}(u,v)+h(v)-<!--\; -\; -->h(u)$$d_{uv}\leftarrow {\hat {\delta }}(u,\;v)+h(v)-h(u)$ 
return D

СложностьПравить

Если в алгоритме Дейкстры неубывающая очередь с приоритетами реализована в виде фибоначчиевой кучи, то время работы алгоритма Джонсона равно $O(V^2\log <!--\; \; -->V+VE)$$O(V^{2}\log V+VE)$ . При более простой реализации неубывающей очереди с приоритетами время работы становится равным $O(VE\log <!--\; \; -->V)$$O(VE\log V)$ , но для разреженных графов эта величина в асимптотическом пределе ведёт себя лучше, чем время работы алгоритма Флойда — Уоршелла.

См. такжеПравить

• Алгоритм Дейкстры
• Алгоритм Беллмана — Форда
• Алгоритм Флойда — Уоршелла

СсылкиПравить

• Визуализатор алгоритма

ЛитератураПравить

• Томас Х. Кормен и др. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 726. — ISBN 5-8459-0857-4.
• Томас Х. Кормен и др. Алгоритмы: построение и анализ. — 1-е изд. — М.: МЦНМО, 2004. — С. 523. — ISBN 5-900916-37-5.