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

Шаблон:Алгоритми пошуку графами

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

Алгоритм

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

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

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

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

\hat{ω} (u, v) = ω (u, v) + h (u) - h (v) .

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

Зміна ваги

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

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

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

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

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

Складність

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

Див. також

Посилання

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

Література

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

Зміст