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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Алгоритм[ред.ред. код]

Дано граф 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), але для розріджених графів ця величина в асимптотичному межі веде себе краще, ніж час роботи алгоритму Флойда-Воршелла.

Дивіться також[ред.ред. код]

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

Посилання[ред.ред. код]

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

Література[ред.ред. код]

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