Алгоритм Джонсона

Алгоритм Джонсона дозволяє знайти найкоротші шляхи між усіма парами вершин зваженого орієнтованого графу. Цей алгоритм працює, якщо у графі містяться ребра з додатною чи від'ємною вагою, але відсутні цикли з від'ємною вагою. Названо на честь Д. Б. Джонсона, який опублікував цей алгоритм 1977 року.

Алгоритм

Дано граф $G=(V,E)$ з ваговою функцією $\omega :E\rightarrow R$. Якщо ваги всіх ребер $\omega$ у графі є невід'ємними, то можливо знайти найкоротші шляхи між усіма парами вершин, запустивши алгоритм Дейкстри по одному разу для кожної з вершин. Якщо в графі містяться ребра з від'ємною вагою, але відсутні цикли з від'ємною вагою, то можливо обчислити нову множину ребер з невід'ємними вагами, що дозволяє скористатися попереднім методом. Нова множина, що складається з ваг ребер ${\hat {\omega }}$, повинна відповідати таким властивостям:

• Для всіх ребер $(u,\;v)$ нова вага ${\hat {\omega }}(u,\;v)>0$.
• Для всіх пар вершин $u,\;v\in V$ шлях $p$ є найкоротшим шляхом з вершини $u$ до вершини $v$ з використанням вагової функції $\omega$ тоді й лише тоді, коли $p$ є також найкоротшим шляхом з вершини $u$ до вершини $v$ з ваговою функцією ${\hat {\omega }}$.

Збереження найкоротших шляхів

Лема (Зміна ваг зберігає найкоротші шляхи). Нехай дано зважений орієнтований граф $G=(V,\;E)$ з ваговою функцією $\omega :E\to R$, і нехай $h:V\to R$ — довільна функція, що відображує вершини на дійсні числа. Для кожного ребра $(u,\;v)\in E$ визначмо

${\hat {\omega }}(u,\;v)=\omega (u,\;v)+h(u)-h(v).$

Нехай $p=\langle v_{0},\;v_{1},\;\ldots ,\;v_{k}\rangle$ є довільним шляхом з вершини $v_{0}$ до вершини $v_{k}$. $p$ є найкоротшим шляхом з ваговою функцією $\omega$ тоді й лише тоді, коли він є найкоротшим шляхом з ваговою функцією ${\hat {\omega }}$, тобто рівність $\omega (p)=\delta (v_{0},\;v_{k})$ є рівносильною рівності ${\hat {\omega }}(p)={\hat {\delta }}(v_{0},\;v_{k})$. Крім того, граф $G$ містить цикл з від'ємною вагою з використанням вагової функції $\omega$ тоді й лише тоді, коли він містить цикл з від'ємною вагою з використанням вагової функції ${\hat {\omega }}$.

Зміна ваги

1. Для даного графу створімо новий граф $G'=(V',\;E')$, де $V'=V\cup \{s\}$, для деякої нової вершини $s\not \in V$, а $E'=E\cup \{(s,\;v):v\in V\}$.
2. Розширмо вагову функцію $\omega$ таким чином, щоби для всіх вершин $v\in V$ зберігалася рівність $\omega (s,\;v)=0$.
3. Далі визначмо для всіх вершин $v\in V'$ величину $h(v)=\delta (s,\;v)$ та нові ваги для всіх ребер ${\hat {\omega }}(u,\;v)=\omega (u,\;v)+h(u)-h(v)\geqslant 0$.

Основна процедура

В алгоритмі Джонсона використовують алгоритм Беллмана — Форда та алгоритм Дейкстри, втілені у вигляді підпрограм. Ребра зберігають у вигляді переліків суміжних вершин. Алгоритм повертає звичайну матрицю $D=d_{ij}$ розміром $|V|\times |V|$, де $d_{ij}=\delta (i,\;j)$, або видає повідомлення про те, що вхідний граф містить цикл із від'ємною вагою.

Алгоритм Джонсона

 Збудувати граф $G'$
 if Bellman_Ford $(G',\;\omega ,\;s)$ = FALSE
    then print «Вхідний граф містить цикл з від'ємною вагою»
    else for для кожної $v\in V'$
         do призначити величині $h(v)$ значення $\delta (s,\;v)$,
            обчислене алгоритмом Беллмана — Форда
         for для кожного ребра $(u,\;v)\in E'$
             do ${\hat {\omega }}(u,\;v)\leftarrow \omega (u,\;v)+h(u)-h(v)$
         for для кожної вершини $u\in V$
             do обчислення за допомогою алгоритму Дейкстри
             $(G,\;{\hat {\omega }},\;u)$ величин ${\hat {\delta }}(u,\;v)$
             для всіх вершин $v\in V$
             for для кожної вершини $v\in V$
                 do $d_{uv}\leftarrow {\hat {\delta }}(u,\;v)+h(v)-h(u)$
    return D

Складність

Якщо в алгоритмі Дейкстри неспадну чергу з пріоритетами втілено у вигляді фібоначчієвої купи, то тривалість роботи алгоритму Джонсона дорівнює $O(V^{2}\log V+VE)$. За простішого втілення неспадної черги з пріоритетами тривалість роботи стає рівною $O(VE\log V)$, але для розріджених графів ця величина в асимптотичній границі поводиться краще, ніж тривалість роботи алгоритму Флойда — Воршелла.

Див. також

• Алгоритм Дейкстри
• Алгоритм Беллмана — Форда
• Алгоритм Флойда — Воршелла

Посилання

• Унаочнювач алгоритму

Література

• Томас Х. Кормен и др. Алгоритмы: построение и анализ. — 2-е изд. — М. : Издательский дом «Вильямс», 2007. — 726 с. — ISBN 5-8459-0857-4. (рос.)
• Томас Х. Кормен и др. Алгоритмы: построение и анализ. — 1-е изд. — М. : МЦНМО, 2004. — 523 с. — ISBN 5-900916-37-5. (рос.)