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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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