|
|
| Строка 1: |
Строка 1: |
| − | '''Алгоритм Джонсона''' находит кратчайшие пути между всеми парами вершин взвешенного ориентированного графа с положительными или отрицательными ребрами. Данный алгоритм работает правильно, если в графе отсутствуют отрицательные циклы.
| |
| − |
| |
| − | == Алгоритм ==
| |
| − |
| |
| | === Сохранение кратчайших путей === | | === Сохранение кратчайших путей === |
| − | Пусть задана потенциальная функция: <tex>\phi: V \rightarrow \mathbb{R}. \; uv \in E </tex> - ребро: обозначим <tex> w_\phi(uv) = w(uv) + \phi(u) - \phi(v) </tex> | + | Пусть задана потенциальная функция: <tex>\phi: V \rightarrow \mathbb{R}. </tex> |
| | + | Введем обозначение <tex> w_\phi(uv) = w(uv) + \phi(u) - \phi(v), \; uv \in E. </tex> |
| | {{Лемма | | {{Лемма |
| | |statement= | | |statement= |
| Строка 21: |
Строка 18: |
| | :Отсюда, <tex>w(P) < w(Q)</tex> | | :Отсюда, <tex>w(P) < w(Q)</tex> |
| | }} | | }} |
| − |
| |
| − | === Теорема о существовании потенциальной функции ===
| |
| − | {{Теорема
| |
| − | |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.
| |
