Знайдіть найкоротший шлях між двома точками на графіку за допомогою алгоритму Дейкстри

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

Графік - це ряд вузлів, з'єднаних ребрами. Графіки можуть бути зваженими (ребра несуть значення) і спрямованими (ребра мають напрямок).

Деякими додатками цього є оптимізація траєкторії польоту або 6 градусів Кевіна Бекона.

Алгоритм Дейкстри

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

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

Зображення рівнів коду

Крок 0:

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

Давайте встановимо значення на кожному вузлі на позитивну нескінченність, а значення на початковому вузлі - на нуль.

Крок 1:

Подивіться на всі вузли, що безпосередньо прилягають до початкового вузла. Значення, які несуть ребра, що з'єднують старт і ці сусідні вузли, є найкоротшими відстанями до кожного відповідного вузла.

Запишіть ці відстані на вузол - перезаписуючи нескінченність - а також перекресліть вузли, що означає, що знайдено їх найкоротший шлях.

Крок 2:

Виберіть один із вузлів, для якого був розрахований найкоротший шлях, ми будемо називати це нашим стрижнем. Подивіться на сусідні з ним вузли (ми їх називатимемо нашими вузлами призначення) та відстані, що їх розділяють.

Для кожного вузла призначення:

  • Якщо значення в зведеній частині плюс крайове значення, що з’єднує його, складає менше значення цільового вузла, оновіть його значення, оскільки знайдено новий коротший шлях.
  • Якщо всі маршрути до цього вузла призначення вивчені, його можна перекреслити.

Крок 3:

Повторюйте крок 2, поки всі вузли не будуть перекреслені. Тепер у нас є графік, де значення, що зберігаються в будь-якому вузлі, будуть найменшою відстанню до нього від початкового вузла.

Більше інформації:

Детальніше про алгоритм Дейкстри

Інші алгоритми найкоротшого шляху