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

Алгоритми пошуку графами та деревами
α–β A* B*^[en] Бахромовий^[en] Беллмана — Форда Британського музею^[en] Борувки В глибину В ширину Гілок та меж D* Двоспрямований Дейкстри Джонсона Едмондса З вертанням зворотний перехід З ітеративним заглибленням З обмеженням глибини IDA*^[en] Крускала Лексикографічний у ширину На стрибкових точках^[en] Перший-найліпший Прима Променевий SMA* Сходження на вершину Флойда — Воршелла
Переліки
Алгоритми на графах Алгоритми пошуку Список алгоритмів на графах
Пов'язані теми
Динамічне програмування Пошукова гра Пошук по графу Обхід дерева
п о р

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

Алгоритм

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

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

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

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

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

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

Зміна ваги

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

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

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

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

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

Складність

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

Див. також

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

Посилання

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

Література

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