205
правок
Изменения
м
'''Алгоритм Джонсона''' находит кратчайшие пути между всеми парами вершин взвешенного ориентированного графа с положительными или отрицательными ребрами. Данный алгоритм работает правильно, если в графе отсутствуют отрицательные циклы.
== Алгоритм ==
=== Теорема о существовании потенциальной функции ===
{{Теорема
|statement=
В графе <tex>G</tex> нет отрицательных циклов <tex>\Leftrightarrow</tex> существует потенциальная функция <tex> \phi:\; \forall uv \in E\; w_\phi(uv) \ge 0 </tex>
|proof=
<tex>\Leftarrow) </tex> <tex>C</tex> - цикл в графе <tex>G</tex>
:<tex>w(C) = \phi(u_1) + w(C) - \phi(u_1) = w_\phi(C) \ge 0</tex>
<tex>\Rightarrow) </tex> Добавим вершину <tex>s</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>\delta(s,\;u) + w(uv) = </tex> {какой-то путь <tex>s \rightsquigarrow v</tex>}.
:<tex>\delta(s,\;v) =</tex> {минимальный путь <tex>s \rightsquigarrow v</tex>}.
:Следовательно, <tex>w_\phi(uv) \ge 0</tex>
}}
=== Псевдокод ===
В алгоритме Джонсона используется [[алгоритм Форда-Беллмана]] и [[алгоритм Дейкстры]]. Алгоритм возврашает обычную матрицу <tex>D = d_{ij}</tex> размером <tex>|V|\times |V|</tex>, где <tex>d_{ij} = \delta(i,\;j)</tex>, или выдает сообщение о том, что входной граф содержит цикл с отрицательным весом.
Алгоритм Джонсона
Строится граф <tex>G' = (V',\;E')</tex>, где <tex>V' = V \cup \{s\}</tex>,
для некоторой новой вершины <tex>s \not\in V</tex>, а <tex>E' = E \cup \{(s,\;v): v \in V\}</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>w_\phi(u,\;v) \leftarrow w(u,\;v) + \phi(u) - \phi(v)</tex>
'''for''' для каждой вершины <tex>u \in V</tex>
'''do''' вычисление с помощью алгоритма Дейкстры
<tex>(G,\;w_\phi,\;u)</tex> величин <tex>\delta_\phi(u,\;v)</tex>
для всех вершин <tex>v \in V</tex>
'''for''' для каждой вершины <tex>v \in V</tex>
'''do''' <tex>d_{uv} \leftarrow \delta_\phi(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>.
== См. также ==
* [[Алгоритм Дейкстры]]
* [[Алгоритм Форда-Беллмана]]
* [[Алгоритм Флойда]]
* [http://rain.ifmo.ru/cat/view.php/vis/graph-paths/johnson-2001 Визуализатор алгоритма]
== Литература ==
* ''Кормен Т., Лейзерсон Ч., Ривест Р.'' Алгоритмы: построение и анализ.[http://wmate.ru/ebooks/?dl=380&mirror=1] — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.
→Сохранение кратчайших путей
=== Сохранение кратчайших путей ===
Пусть задана потенциальная функция: <tex>\phi: V \rightarrow \mathbb{R}. \; uv \in E </tex> - ребро: обозначим Введем обозначение <tex> w_\phi(uv) = w(uv) + \phi(u) - \phi(v) , \; uv \in E. </tex>
{{Лемма
|statement=
:Отсюда, <tex>w(P) < w(Q)</tex>
}}
