Изменения

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

Пусть есть потенциальная функция: Утверждается, что если какой-то путь <tex> P </tex> был кратчайшим относительно весовой функции <tex>\phi: V \rightarrow \mathbb{R}, \; uv omega </tex> - ребро, тогда то он будет кратчайшим и относительно новой весовой функции <tex> w_\phi(uv) = w(uv) + \phi(u) - omega_\phi(v) varphi </tex>. 

Пусть <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>

:Рассмотрим путь <tex>w_P: \;u_0 \rightarrow u_1 \rightarrow u_2 \phirightarrow \ldots \rightarrow u_k </tex> :Его вес с новой весовой функцией равен <tex>\omega_\varphi(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) + ... </tex> <tex>- \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>

 В графе <tex>G</tex> нет отрицательных циклов <tex>\Leftrightarrow</tex> существует потенциальная функция <tex> \phi:\; \forall u,vuv \in E\; w_\phiomega_\varphi(uv) \ge geqslant 0 </tex> 

<tex>\Leftarrow </tex>: Рассмотрим произвольный <tex>C</tex> — цикл в графе <tex>G</tex> :По лемме, его вес равен <tex>w\omega(C) = \phiomega_\varphi(u_1C) + w\varphi(Сu_0) - \phivarphi(u_1u_0) = w_\phiomega_\varphi(C) \ge 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>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> '''function''' Johnson(G): '''int[][]''' '''if''' BellmanFord<tex>(G',\;\omega,\;s)</tex> == ''false'' print "Входной граф содержит цикл с отрицательным весом" '''return''' <tex>\varnothing</tex> '''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>G'</tex> '''if''' Bellman_Ford<tex>(G',\;\omega,\;s)</tex> == FALSE '''then''' out << «Входной граф содержит цикл с отрицательным весом» '''else''' '''for''' для Затем из каждой <tex>v \in V'</tex> '''do''' присвоить величине <tex>\phi(v)</tex> значение <tex>\delta(s,\;v)</tex>, вычисленное алгоритмом Беллмана — Форда '''for''' вершины запускается алгоритм Дейкстры для каждого ребра <tex>(u,\;v) \in E'</tex> '''do''' <tex>\hat{\omega}(u,\;v) \leftarrow \omega(uсоставления искомой матрицы. Так как все веса ребер теперь неотрицательны,\;v) + \phi(u) - \phi(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) + \phi(v) - \phi(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.