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

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

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

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

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

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

Збереження найкоротших шляхів[ред. | ред. код]

Лема (Зміна ваг зберігає найкоротші шляхи). Нехай дано зважений орієнтований граф з ваговою функцією , і нехай  — довільна функція, що відображує вершини на дійсні числа. Для кожного ребра визначмо

Нехай є довільним шляхом з вершини до вершини . є найкоротшим шляхом з ваговою функцією тоді й лише тоді, коли він є найкоротшим шляхом з ваговою функцією , тобто рівність є рівносильною рівності . Крім того, граф містить цикл з від'ємною вагою з використанням вагової функції тоді й лише тоді, коли він містить цикл з від'ємною вагою з використанням вагової функції .

Зміна ваги[ред. | ред. код]

  1. Для даного графу створімо новий граф , де , для деякої нової вершини , а .
  2. Розширмо вагову функцію таким чином, щоби для всіх вершин зберігалася рівність .
  3. Далі визначмо для всіх вершин величину та нові ваги для всіх ребер .

Основна процедура[ред. | ред. код]

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

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

 Збудувати граф 
 if Bellman_Ford  = FALSE
    then print «Вхідний граф містить цикл з від'ємною вагою»
    else for для кожної 
         do призначити величині  значення ,
            обчислене алгоритмом Беллмана — Форда
         for для кожного ребра 
             do 
         for для кожної вершини 
             do обчислення за допомогою алгоритму Дейкстри
              величин 
             для всіх вершин 
             for для кожної вершини 
                 do 
    return D

Складність[ред. | ред. код]

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

Див. також[ред. | ред. код]

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

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