81
правка
Изменения
Новая страница: «'''Алгоритм Джонсона''' находит кратчайшие пути между всеми парами вершин во взвешенном о...»
'''Алгоритм Джонсона''' находит кратчайшие пути между всеми парами вершин во взвешенном ориентированном графе с любыми весами ребер, но не имеющем отрицательных циклов.
== Алгоритм ==
=== Описание ===
Алгоритм Джонсона позволяет найти кратчайшие пути между всеми парами вершин в течение времени <tex> O(V^2\log(V) + VE) </tex>. Для разреженных графов этот алгоритм ведет себя асимптотически быстрее алгоритма Флойда. Этот алгоритм либо возвращает матрицу кратчайших расстояний между всеми парами вершин, либо сообщение о том, что в графе существует цикл отрицательной длины.
В этом алгоритме используется метод '''изменения веса''' (англ. reweighting). Суть его заключается в том, что для заданного графа <tex> G </tex> строится новая весовая функция <tex> \omega_\varphi </tex>, неотрицательная для всех ребер графа <tex> G </tex> и сохраняющая кратчайшие пути. Такая весовая функция строится с помощью так называемой '''потенциальной''' функции.
Пусть <tex> \varphi : V \rightarrow \mathbb R </tex> — произвольное отображение из множества вершин в вещественные числа. Тогда новой весовой функцией будет <tex> \omega_\varphi(u, v) = \omega(u, v) + \varphi(u) - \varphi(v) </tex>.
Такая потенциальная функция строится при помощи добавлении фиктивной вершины в <tex> G </tex>, из которой проведены ребра нулевого веса во все остальные вершины и запуском алгоритма Форда-Беллмана из нее. На этом же этапе мы сможем обнаружить наличие отрицательного цикла в графе.
Теперь, когда мы знаем, что веса всех ребер неотрицательны, и кратчайшие пути сохранятся, можно запустить алгоритм Дейкстры из каждой вершины и таким образом найти кратчайшие расстояния между всеми парами вершин.
=== Сохранение кратчайших путей ===
Утверждается, что если какой-то путь <tex> P </tex> был кратчайшим относительно весовой функции <tex> \omega </tex>, то он будет кратчайшим и относительно новой весовой функции <tex> \omega_\varphi </tex>.
{{Лемма
|statement=
Пусть <tex>P,\; Q </tex> {{---}} два пути <tex> a \rightsquigarrow b\;</tex> и <tex>\omega(P) < \omega(Q).</tex> Тогда <tex>\forall \varphi: \; \omega_\varphi(P) < \omega_\varphi(Q)</tex>
|proof=
:Рассмотрим путь <tex>P: \;u_0 \rightarrow u_1 \rightarrow u_2 \rightarrow ... \rightarrow u_k </tex>
:Его вес с новой весовой функцией равен <tex>\omega_\varphi(P) = \omega_\varphi(u_0u_1) + \omega_\varphi(u_1u_2) + ... + \omega_\varphi(u_{k-1}u_k) </tex>.
:Вставим определение функции <tex> \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) </tex>
:Заметим, что потенциалы все промежуточных вершин в пути сократятся. <tex> \omega_\varphi(P) = \varphi(u_0) + \omega(P) - \varphi(u_k)</tex>
:По изначальному предположению: <tex>\omega(P) < \omega(Q)</tex>. С новой весовой функцией веса соответствующих путей будут:
:<tex>\omega_\varphi(P) = \varphi(a) + \omega(P) - \varphi(b)</tex>
:<tex>\omega_\varphi(Q) = \varphi(a) + \omega(Q) - \varphi(b)</tex>
:Отсюда, <tex>\omega_\varphi(P) < \omega_\varphi(Q)</tex>
}}
=== Теорема о существовании потенциальной функции ===
{{Теорема
|statement=
В графе <tex>G</tex> нет отрицательных циклов <tex>\Leftrightarrow</tex> существует потенциальная функция <tex> \phi:\; \forall uv \in E\; \omega_\varphi(uv) \geqslant 0 </tex>
|proof=
<tex>\Leftarrow </tex>: Рассмотрим произвольный <tex>C</tex> - цикл в графе <tex>G</tex>
:По лемме, его вес равен <tex> \omega(C) = \omega_\varphi(C) - \varphi(u_0) - \varphi(u_0) = \omega_\varphi(C) \geqslant 0</tex>
<tex>\Rightarrow </tex>: Добавим фиктивную вершину <tex>s</tex> в граф, а также ребра <tex> s \to u </tex> весом <tex> 0 </tex> для всех <tex> u </tex>.
:Обозначим <tex>\delta(u,v)</tex> как минимальное расстояние между вершинами <tex>u,\; v</tex>.
:Введем потенциальную функцию <tex> \phi </tex> следующим образом: <tex>\phi(u) = \delta(s,u)</tex>
:Рассмотрим вес произвольного ребра <tex> uv \in E </tex>: <tex>\omega_\phi(uv) = \phi(u) + \omega(uv) - \phi(v) = \delta(s, u) + \omega(uv) - \delta(s, v)</tex>.
:Поскольку <tex>\delta(s, u) + \omega(uv) </tex> {{---}} вес какого-то пути <tex> s \rightsquigarrow v </tex>, а <tex> \delta(s, v) </tex> {{---}} вес кратчайшего пути <tex> s \rightsquigarrow v</tex>, то <tex> \delta(s, u) + \omega(uv) \geqslant \delta(s, v) \Rightarrow \delta(s, u) + \omega(uv) - \delta(s, v) = \omega_\varphi(uv) \geqslant 0 </tex>.
}}
=== Псевдокод ===
Предварительно построим граф <tex>G' = (V',\;E')</tex>, где <tex>V' = V \cup \{s\}</tex>, <tex>s \not\in V</tex>, а <tex>E' = E \cup \{(s,\;v): \omega(s, v) = 0,\ v \in V \}</tex>
'''if''' Bellman_Ford<tex>(G',\;\omega,\;s)</tex> == FALSE
'''then''' print "Входной граф содержит цикл с отрицательным весом"
'''else''' '''for''' <tex>v \in V'</tex>
<tex>\varphi(v)</tex> = <tex>\delta(s,\;v)</tex> <font color = green>//<tex>\delta(s,\;v)</tex> вычислено алгоритмом Беллмана — Форда</font>
'''for''' <tex>(u,\;v) \in E'</tex>
<tex>\omega_\varphi(u,\;v)</tex> = <tex> \omega(u,\;v) + \varphi(u) - \varphi(v)</tex>
'''for''' <tex>u \in V</tex>
Dijkstra<tex>(G,\;\omega_\varphi,\;u)</tex>
'''for''' <tex>v \in V</tex>
<tex>d_{uv} \leftarrow \delta_\varphi(u,\;v) + \varphi(v) - \varphi(u)</tex>
'''return''' <tex>d</tex>
Итого, в начале алгоритм Форда-Беллмана либо строит потенциальную функцию такую, что после перевзвешивания все веса ребер будут неотрицательны, либо выдает сообщение о том, что в графе присутствует отрицательный цикл.
Затем из каждой вершины запускается алгоритм Дейкстры для составления искомой матрицы. Так как все веса ребер теперь неотрицательны, алгоритм Дейкстры будет работать корректно. А поскольку перевзвешивание таково, что кратчайшие пути относительно обеих весовых функций совпадают, алгоритм Джонсона в итоге корректно найдет все кратчайшие пути между всеми парами вершин.
== Сложность ==
Алгоритм Джонсона работает за <tex>O(VE + VD)</tex>, где <tex>O(D)</tex> — время работы [[Алгоритм Дейкстры| алгоритма Дейкстры]]. Если в алгоритме Дейкстры неубывающая очередь с приоритетами реализована в виде [[Фибоначчиевы кучи| фибоначчиевой кучи]], то время работы алгоритма Джонсона есть <tex>O(V^2\log V + V E)</tex>. В случае реализации очереди с приоритетами в виде двоичной кучи время работы равно <tex>O(V E \log V)</tex>.
== См. также ==
* [[Алгоритм Дейкстры]]
* [[Алгоритм Форда-Беллмана]]
* [[Алгоритм Флойда]]
* [http://rain.ifmo.ru/cat/view.php/vis/graph-paths/johnson-2001 Визуализатор алгоритма]
== Источники информации ==
* ''Кормен Т., Лейзерсон Ч., Ривест Р.'' Алгоритмы: построение и анализ. 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.
== Алгоритм ==
=== Описание ===
Алгоритм Джонсона позволяет найти кратчайшие пути между всеми парами вершин в течение времени <tex> O(V^2\log(V) + VE) </tex>. Для разреженных графов этот алгоритм ведет себя асимптотически быстрее алгоритма Флойда. Этот алгоритм либо возвращает матрицу кратчайших расстояний между всеми парами вершин, либо сообщение о том, что в графе существует цикл отрицательной длины.
В этом алгоритме используется метод '''изменения веса''' (англ. reweighting). Суть его заключается в том, что для заданного графа <tex> G </tex> строится новая весовая функция <tex> \omega_\varphi </tex>, неотрицательная для всех ребер графа <tex> G </tex> и сохраняющая кратчайшие пути. Такая весовая функция строится с помощью так называемой '''потенциальной''' функции.
Пусть <tex> \varphi : V \rightarrow \mathbb R </tex> — произвольное отображение из множества вершин в вещественные числа. Тогда новой весовой функцией будет <tex> \omega_\varphi(u, v) = \omega(u, v) + \varphi(u) - \varphi(v) </tex>.
Такая потенциальная функция строится при помощи добавлении фиктивной вершины в <tex> G </tex>, из которой проведены ребра нулевого веса во все остальные вершины и запуском алгоритма Форда-Беллмана из нее. На этом же этапе мы сможем обнаружить наличие отрицательного цикла в графе.
Теперь, когда мы знаем, что веса всех ребер неотрицательны, и кратчайшие пути сохранятся, можно запустить алгоритм Дейкстры из каждой вершины и таким образом найти кратчайшие расстояния между всеми парами вершин.
=== Сохранение кратчайших путей ===
Утверждается, что если какой-то путь <tex> P </tex> был кратчайшим относительно весовой функции <tex> \omega </tex>, то он будет кратчайшим и относительно новой весовой функции <tex> \omega_\varphi </tex>.
{{Лемма
|statement=
Пусть <tex>P,\; Q </tex> {{---}} два пути <tex> a \rightsquigarrow b\;</tex> и <tex>\omega(P) < \omega(Q).</tex> Тогда <tex>\forall \varphi: \; \omega_\varphi(P) < \omega_\varphi(Q)</tex>
|proof=
:Рассмотрим путь <tex>P: \;u_0 \rightarrow u_1 \rightarrow u_2 \rightarrow ... \rightarrow u_k </tex>
:Его вес с новой весовой функцией равен <tex>\omega_\varphi(P) = \omega_\varphi(u_0u_1) + \omega_\varphi(u_1u_2) + ... + \omega_\varphi(u_{k-1}u_k) </tex>.
:Вставим определение функции <tex> \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) </tex>
:Заметим, что потенциалы все промежуточных вершин в пути сократятся. <tex> \omega_\varphi(P) = \varphi(u_0) + \omega(P) - \varphi(u_k)</tex>
:По изначальному предположению: <tex>\omega(P) < \omega(Q)</tex>. С новой весовой функцией веса соответствующих путей будут:
:<tex>\omega_\varphi(P) = \varphi(a) + \omega(P) - \varphi(b)</tex>
:<tex>\omega_\varphi(Q) = \varphi(a) + \omega(Q) - \varphi(b)</tex>
:Отсюда, <tex>\omega_\varphi(P) < \omega_\varphi(Q)</tex>
}}
=== Теорема о существовании потенциальной функции ===
{{Теорема
|statement=
В графе <tex>G</tex> нет отрицательных циклов <tex>\Leftrightarrow</tex> существует потенциальная функция <tex> \phi:\; \forall uv \in E\; \omega_\varphi(uv) \geqslant 0 </tex>
|proof=
<tex>\Leftarrow </tex>: Рассмотрим произвольный <tex>C</tex> - цикл в графе <tex>G</tex>
:По лемме, его вес равен <tex> \omega(C) = \omega_\varphi(C) - \varphi(u_0) - \varphi(u_0) = \omega_\varphi(C) \geqslant 0</tex>
<tex>\Rightarrow </tex>: Добавим фиктивную вершину <tex>s</tex> в граф, а также ребра <tex> s \to u </tex> весом <tex> 0 </tex> для всех <tex> u </tex>.
:Обозначим <tex>\delta(u,v)</tex> как минимальное расстояние между вершинами <tex>u,\; v</tex>.
:Введем потенциальную функцию <tex> \phi </tex> следующим образом: <tex>\phi(u) = \delta(s,u)</tex>
:Рассмотрим вес произвольного ребра <tex> uv \in E </tex>: <tex>\omega_\phi(uv) = \phi(u) + \omega(uv) - \phi(v) = \delta(s, u) + \omega(uv) - \delta(s, v)</tex>.
:Поскольку <tex>\delta(s, u) + \omega(uv) </tex> {{---}} вес какого-то пути <tex> s \rightsquigarrow v </tex>, а <tex> \delta(s, v) </tex> {{---}} вес кратчайшего пути <tex> s \rightsquigarrow v</tex>, то <tex> \delta(s, u) + \omega(uv) \geqslant \delta(s, v) \Rightarrow \delta(s, u) + \omega(uv) - \delta(s, v) = \omega_\varphi(uv) \geqslant 0 </tex>.
}}
=== Псевдокод ===
Предварительно построим граф <tex>G' = (V',\;E')</tex>, где <tex>V' = V \cup \{s\}</tex>, <tex>s \not\in V</tex>, а <tex>E' = E \cup \{(s,\;v): \omega(s, v) = 0,\ v \in V \}</tex>
'''if''' Bellman_Ford<tex>(G',\;\omega,\;s)</tex> == FALSE
'''then''' print "Входной граф содержит цикл с отрицательным весом"
'''else''' '''for''' <tex>v \in V'</tex>
<tex>\varphi(v)</tex> = <tex>\delta(s,\;v)</tex> <font color = green>//<tex>\delta(s,\;v)</tex> вычислено алгоритмом Беллмана — Форда</font>
'''for''' <tex>(u,\;v) \in E'</tex>
<tex>\omega_\varphi(u,\;v)</tex> = <tex> \omega(u,\;v) + \varphi(u) - \varphi(v)</tex>
'''for''' <tex>u \in V</tex>
Dijkstra<tex>(G,\;\omega_\varphi,\;u)</tex>
'''for''' <tex>v \in V</tex>
<tex>d_{uv} \leftarrow \delta_\varphi(u,\;v) + \varphi(v) - \varphi(u)</tex>
'''return''' <tex>d</tex>
Итого, в начале алгоритм Форда-Беллмана либо строит потенциальную функцию такую, что после перевзвешивания все веса ребер будут неотрицательны, либо выдает сообщение о том, что в графе присутствует отрицательный цикл.
Затем из каждой вершины запускается алгоритм Дейкстры для составления искомой матрицы. Так как все веса ребер теперь неотрицательны, алгоритм Дейкстры будет работать корректно. А поскольку перевзвешивание таково, что кратчайшие пути относительно обеих весовых функций совпадают, алгоритм Джонсона в итоге корректно найдет все кратчайшие пути между всеми парами вершин.
== Сложность ==
Алгоритм Джонсона работает за <tex>O(VE + VD)</tex>, где <tex>O(D)</tex> — время работы [[Алгоритм Дейкстры| алгоритма Дейкстры]]. Если в алгоритме Дейкстры неубывающая очередь с приоритетами реализована в виде [[Фибоначчиевы кучи| фибоначчиевой кучи]], то время работы алгоритма Джонсона есть <tex>O(V^2\log V + V E)</tex>. В случае реализации очереди с приоритетами в виде двоичной кучи время работы равно <tex>O(V E \log V)</tex>.
== См. также ==
* [[Алгоритм Дейкстры]]
* [[Алгоритм Форда-Беллмана]]
* [[Алгоритм Флойда]]
* [http://rain.ifmo.ru/cat/view.php/vis/graph-paths/johnson-2001 Визуализатор алгоритма]
== Источники информации ==
* ''Кормен Т., Лейзерсон Ч., Ривест Р.'' Алгоритмы: построение и анализ. 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.
