Алгоритм Джонсона находит кратчайшие пути между всеми парами вершин взвешенного ориентированного графа с положительными или отрицательными ребрами. Данный алгоритм работает правильно, если в графе отсутствуют отрицательные циклы.
Алгоритм
Сохранение кратчайших путей
Пусть задана потенциальная функция: [math]\phi: V \rightarrow \mathbb{R}. \; uv \in E [/math] - ребро: обозначим [math] w_\phi(uv) = w(uv) + \phi(u) - \phi(v) [/math]
| Лемма: |
Пусть [math]P,\; Q : a \rightsquigarrow b.\; w(P) \lt w(Q)[/math]. Тогда [math]\forall \phi: \; w_\phi(P) \lt w_\phi(Q)[/math] |
| Доказательство: |
| [math]\triangleright[/math] |
- [math]P: \;u_0 \rightarrow u_1 \rightarrow u_2 \rightarrow ... \rightarrow u_k [/math]
- [math]w_\phi(P) = w_\phi(u_0u_1) + w_\phi(u_1u_2) + ... + w_\phi(u_{k-1}u_k) = \phi(u_0) + w(u_0u_1) - \phi(u_1) + ... + \phi(u_{k-1}) + w(u_{k-1}u_k) - \phi(u_k) = \phi(u_0) + w(P) - \phi(u_k)[/math]
- [math]w_\phi(P) \lt w_\phi(Q)[/math]
- [math]w_\phi(P) = \phi(a) + w(P) - \phi(b)[/math]
- [math]w_\phi(Q) = \phi(a) + w(Q) - \phi(b)[/math]
- Отсюда, [math]w(P) \lt w(Q)[/math]
|
| [math]\triangleleft[/math] |
Теорема о существовании потенциальной функции
| Теорема: |
В графе [math]G[/math] нет отрицательных циклов [math]\Leftrightarrow[/math] существует потенциальная функция [math] \phi:\; \forall uv \in E\; w_\phi(uv) \ge 0 [/math] |
| Доказательство: |
| [math]\triangleright[/math] |
|
[math]\Leftarrow) [/math] [math]C[/math] - цикл в графе [math]G[/math]
- [math]w(C) = \phi(u_1) + w(C) - \phi(u_1) = w_\phi(C) \ge 0[/math]
[math]\Rightarrow) [/math] Добавим вершину [math]s[/math] в граф, соединим её со всеми вершинами графа [math]G[/math] ребрами весом [math]w = 0[/math].
- [math]\phi(u) = \delta(s,\;u)[/math]
- [math]w_\phi(uv) = \phi(u) + w(uv) - \phi(v) = \delta(s,\;u) + w(uv) - \delta(s,\;v)[/math].
- [math]\delta(s,\;u) + w(uv) = [/math] {какой-то путь [math]s \rightsquigarrow v[/math]}.
- [math]\delta(s,\;v) =[/math] {минимальный путь [math]s \rightsquigarrow v[/math]}.
- Следовательно, [math]w_\phi(uv) \ge 0[/math]
|
| [math]\triangleleft[/math] |
Псевдокод
В алгоритме Джонсона используется алгоритм Форда-Беллмана и алгоритм Дейкстры. Алгоритм возврашает обычную матрицу [math]D = d_{ij}[/math] размером [math]|V|\times |V|[/math], где [math]d_{ij} = \delta(i,\;j)[/math], или выдает сообщение о том, что входной граф содержит цикл с отрицательным весом.
Алгоритм Джонсона
Строится граф [math]G' = (V',\;E')[/math], где [math]V' = V \cup \{s\}[/math],
для некоторой новой вершины [math]s \not\in V[/math], а [math]E' = E \cup \{(s,\;v): v \in V\}[/math]
if Bellman_Ford[math](G',\;\omega,\;s)[/math] == FALSE
then out << «Входной граф содержит цикл с отрицательным весом»
else for для каждой [math]v \in V'[/math]
do присвоить величине [math]\phi(v)[/math] значение [math]\delta(s,\;v)[/math],
вычисленное алгоритмом Беллмана — Форда
for для каждого ребра [math](u,\;v) \in E'[/math]
do [math]w_\phi(u,\;v) \leftarrow w(u,\;v) + \phi(u) - \phi(v)[/math]
for для каждой вершины [math]u \in V[/math]
do вычисление с помощью алгоритма Дейкстры
[math](G,\;w_\phi,\;u)[/math] величин [math]\delta_\phi(u,\;v)[/math]
для всех вершин [math]v \in V[/math]
for для каждой вершины [math]v \in V[/math]
do [math]d_{uv} \leftarrow \delta_\phi(u,\;v) + \phi(v) - \phi(u)[/math]
return D
Сложность
Алгоритм Джонсона работает за [math]O(VE + VD)[/math], где [math]O(D)[/math] - время работы алгоритма Дейкстры. Если в алгоритме Дейкстры неубывающая очередь с приоритетами реализована в виде фибоначчиевой кучи, то время работы алгоритма Джонсона равно [math]O(V^2\log V + V E)[/math].
См. также
Литература
- Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ.[1] — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.
