Изменения

'''Алгоритм Джонсона''' (англ. ''Johnson's algorithm'') находит кратчайшие пути между всеми парами вершин взвешенного ориентированного графа во взвешенном ориентированном графе с положительными или отрицательными ребрамилюбыми весами ребер, но без не имеющем отрицательных циклов.

:Заметим, что потенциалы все промежуточных вершин в пути сократятся. <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'</tex> '''if''' Bellman_Ford<tex>(G'Итого,\;\omegaв начале алгоритм Форда-Беллмана либо строит потенциальную функцию такую,\;s)</tex> == FALSE '''then''' out << «Входной граф содержит цикл с отрицательным весом» '''else''' '''for''' для каждой <tex>v \in V'</tex> '''do''' присвоить величине <tex>h(v)</tex> значение <tex>\delta(sчто после перевзвешивания все веса ребер будут неотрицательны,\;v)</tex>либо выдает сообщение о том,что в графе присутствует отрицательный цикл. вычисленное алгоритмом Беллмана — Форда '''for''' для каждого ребра <tex>(u,\;v) \in E'</tex> '''do''' <tex>\hat{\omega}(u,\;v) \leftarrow \omega(u,\;v) + h(u) - h(v)</tex> '''for''' для Затем из каждой вершины <tex>u \in V</tex> '''do''' вычисление с помощью алгоритма запускается алгоритм Дейкстры <tex>(Gдля составления искомой матрицы. Так как все веса ребер теперь неотрицательны,\;\hat{\omega}алгоритм Дейкстры будет работать корректно. А поскольку перевзвешивание таково,\;u)</tex> величин <tex>\hat{\delta}(uчто кратчайшие пути относительно обеих весовых функций совпадают,\;v)</tex> для всех алгоритм Джонсона в итоге корректно найдет все кратчайшие пути между всеми парами вершин <tex>v \in V</tex> '''for''' для каждой вершины <tex>v \in V</tex> '''do''' <tex>d_{uv} \leftarrow \hat{\delta}(u,\;v) + h(v) - h(u)</tex> '''return''' D.

Алгоритм Джонсона работает за <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[Категория://wmate.ru/ebooks/?dl=380&mirror=1Кратчайшие пути в графах ]] — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.