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

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

Алгоритм

Дано граф $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)$ і нові ваги для всіх ребер math>\hat{\omega}(u,\;v) = \omega(u,\;v) + h(u) - h(v) \geqslant 0</math>.

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

В алгоритмі Джонсона використовується алгоритм Беллмана-Форда і алгоритм Дейкстри, реалізовані у вигляді підпрограм. Ребра зберігаються у вигляді списків суміжних вершин. Алгоритм повертає звичайну матрицю $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 + V E)$. При простіший реалізації неубутною черги з пріоритетами час роботи стає рівним $O(V E\log V)$, але для розріджених графів ця величина в асимптотичному межі веде себе краще, ніж час роботи алгоритму Флойда-Воршелла.

Дивіться також

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

Посилання

Візуалізатор

Література

• Томас Х. Кормен та ін Алгоритми: побудова й аналіз.