Изменения
Нет описания правки
'''Алгоритм Джонсона''' (англ. ''Johnson's algorithm'') находит кратчайшие пути между всеми парами вершин взвешенного ориентированного графа во взвешенном ориентированном графе с положительными или отрицательными ребрами. Данный алгоритм работает правильнолюбыми весами ребер, если в графе отсутствуют отрицательные циклыно не имеющем отрицательных циклов.
== Алгоритм ==
=== Описание ===
Алгоритм Джонсона позволяет найти кратчайшие пути между всеми парами вершин в течение времени <tex> O(V^2\log(V) + VE) </tex>. Для разреженных графов этот алгоритм ведет себя асимптотически быстрее [[Алгоритм Флойда|алгоритма Флойда]]. Этот алгоритм либо возвращает матрицу кратчайших расстояний между всеми парами вершин, либо сообщение о том, что в графе существует цикл отрицательной длины.
В этом алгоритме используется метод '''изменения веса''' (англ. ''reweighting''). Суть его заключается в том, что для заданного графа <tex> G </tex> строится новая весовая функция <tex> \omega_\varphi </tex>, неотрицательная для всех ребер графа <tex> G </tex> и сохраняющая кратчайшие пути. Такая весовая функция строится с помощью так называемой [[Амортизационный_анализ#.D0.9C.D0.B5.D1.82.D0.BE.D0.B4_.D0.BF.D0.BE.D1.82.D0.B5.D0.BD.D1.86.D0.B8.D0.B0.D0.BB.D0.BE.D0.B2|потенциальной]] функции.
Пусть <tex> \varphi : V \rightarrow \mathbb R </tex> — произвольное отображение из множества вершин в вещественные числа. Тогда новой весовой функцией будет <tex> \omega_\varphi(u, v) = \omega(u, v) + \varphi(u) - \varphi(v) </tex>.
Такая потенциальная функция строится добавлем фиктивной вершины <tex> s </tex> в <tex> G </tex>, из которой проведены ориентированные ребра нулевого веса во все остальные вершины графа, и запуском [[Алгоритм Форда-Беллмана|алгоритма Форда-Беллмана]] из нее (<tex> \varphi(v) </tex> будет равно длине кратчайшего пути из <tex> s </tex> в <tex> v </tex>). На этом же этапе мы сможем обнаружить наличие отрицательного цикла в графе.
Теперь, когда мы знаем, что веса всех ребер неотрицательны, и кратчайшие пути сохранятся, можно запустить [[Алгоритм Дейкстры|алгоритм Дейкстры]] из каждой вершины и таким образом найти кратчайшие расстояния между всеми парами вершин.
=== Сохранение кратчайших путей ===
{{Лемма
|statement=
Пусть <tex>P,\; Q : </tex> {{---}} два пути <tex> a \rightsquigarrow b.\; w</tex> и <tex>\omega(P) < w\omega(Q).</tex>. Тогда <tex>\forall \phivarphi: \; w_\phiomega_\varphi(P) < w_\phiomega_\varphi(Q)</tex>
|proof=
:Рассмотрим путь <tex>w_P: \;u_0 \rightarrow u_1 \rightarrow u_2 \rightarrow \ldots \rightarrow u_k </tex> :Его вес с новой весовой функцией равен <tex>\omega_\phivarphi(P) = w_\phiomega_\varphi(u_1u_2u_0u_1) + w_\phiomega_\varphi(u_2u_3u_1u_2) + ... \ldots + w_\phiomega_\varphi(u_{k-1}u_k) </tex>. :Вставим определение функции <tex> \omega_\varphi : \omega_\varphi(P) = \phivarphi(u_1u_0) + w\omega(u_1u_2u_0u_1) - \phivarphi(u_2u_1) + ... - \phi(u_{k-1})ldots +\phivarphi(u_{k-1}) + w\omega(u_{k-1}u_k) - \phivarphi(u_k) </tex> :Заметим, что потенциалы все промежуточных вершин в пути сократятся. <tex> \omega_\varphi(P) = \phivarphi(u_1u_0) + w\omega(P) - \phivarphi(u_k)</tex>
:По изначальному предположению: <tex>w_\phiomega(P) < w_\phiomega(Q)</tex>. С новой весовой функцией веса соответствующих путей будут:
:<tex>w_\phiomega_\varphi(P) = \phivarphi(a) + w\omega(P) - \phivarphi(b)</tex>
:<tex>w_\phiomega_\varphi(Q) = \phivarphi(a) + w\omega(Q) - \phivarphi(b)</tex>
:Отсюда, <tex>w\omega_\varphi(P) < w\omega_\varphi(Q)</tex>
}}
{{Теорема
|statement=
В графе <tex>G</tex> нет отрицательных циклов тогда и только тогда, когда <tex>\Leftrightarrow</tex> существует потенциальная функция <tex> \phi:\; \forall u,vuv \in E\; w_\phiomega_\varphi(uv) >= \geqslant 0 </tex>
|proof=
<tex>\Leftarrow </tex>:Рассмотрим произвольный <tex>C</tex>w— цикл в графе <tex>G</tex> :По лемме, его вес равен <tex> \omega(C) = \phiomega_\varphi(u_1C) + w\varphi(cu_0) - \phivarphi(u_1u_0) = w_\phiomega_\varphi(C) \geqslant 0</tex> <tex>\Rightarrow </tex>: Добавим фиктивную вершину <tex>s</tex> в граф, а также ребра <tex> s \to u </tex> весом <tex>= 0</tex>для всех <tex> u </tex>.
:Обозначим <tex>\Rightarrowdelta(u,v) </tex> Добавим вершину как минимальное расстояние между вершинами <tex>su,\; v</tex> в граф, соединим её со всеми вершинами графа <tex>G</tex> ребрами весом <tex>w = 0</tex>.:введем потенциальную функцию <tex>\phi(u) = \delta(s,\;u)</tex>
:<tex>w_\phi(uv) = \phi(u) + w(uv) - \phi(v) = \delta(s,\;u) + w(uv) - \delta(s,\;v)</tex>.
:Рассмотрим вес произвольного ребра <tex>uv \in E </tex>: <tex>\omega_\phi(uv) = \phi(u) + \omega(uv) - \phi(v) = \delta(s,\;u) + w\omega(uv) = </tex> {какой-то путь <tex>\delta(s \rightsquigarrow , 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>O(VE + VD)</tex>, где <tex>O(D)</tex> - — время работы [[Алгоритм ДейктсрыДейкстры| алгоритма Дейкстры]]. Если в алгоритме Дейкстры неубывающая очередь с приоритетами реализована в виде [http://ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8%D0%B5%D0%B2%D0%B0_%D0%BA%D1%83%D1%87%D0%B0 [Фибоначчиевы кучи| фибоначчиевой кучи]], то время работы алгоритма Джонсона равно есть <tex>O(V^2\log V + V E)</tex>. В случае реализации очереди с приоритетами в виде двоичной кучи время работы равно <tex>O(V E \log V)</tex>.
== См. также ==
* [[Алгоритм Дейкстры]]
* [[Алгоритм Форда-Беллмана — Форда]]* [[Алгоритм Флойда — Уоршелла]] == Источники информации ==* ''Кормен Т., Лейзерсон Ч., Ривест Р.'' Алгоритмы: построение и анализ. 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.
* [http://rain.ifmo.ru/cat/view.php/vis/graph-paths/johnson-2001 Визуализатор алгоритма]