Пошук найкоротшого шляху між двома точками на графіку є загальною проблемою в структурах даних, особливо при роботі з оптимізацією.
Графік - це ряд вузлів, з'єднаних ребрами. Графіки можуть бути зваженими (ребра несуть значення) і спрямованими (ребра мають напрямок).
Деякими додатками цього є оптимізація траєкторії польоту або 6 градусів Кевіна Бекона.
Алгоритм Дейкстри
Найпоширенішим рішенням цієї проблеми є алгоритм Дейкстри, який оновлює найкоротший шлях між поточним вузлом та усіма його сусідами.
Після оновлення відстані всіх сусідів він рухається до вузла з найменшою відстанню і повторює процес з усіма невідвіданими сусідами. Цей процес триває, поки не буде відвідано весь графік.
Крок 0:
Наш графік повинен бути налаштований, щоб ми могли записати необхідні значення. На будь-якому ребрі ми маємо відстань між двома вузлами, які він з'єднує. На будь-якому вузлі ми маємо найкоротшу відстань від початкового вузла.
Давайте встановимо значення на кожному вузлі на позитивну нескінченність, а значення на початковому вузлі - на нуль.
Крок 1:
Подивіться на всі вузли, що безпосередньо прилягають до початкового вузла. Значення, які несуть ребра, що з'єднують старт і ці сусідні вузли, є найкоротшими відстанями до кожного відповідного вузла.
Запишіть ці відстані на вузол - перезаписуючи нескінченність - а також перекресліть вузли, що означає, що знайдено їх найкоротший шлях.
Крок 2:
Виберіть один із вузлів, для якого був розрахований найкоротший шлях, ми будемо називати це нашим стрижнем. Подивіться на сусідні з ним вузли (ми їх називатимемо нашими вузлами призначення) та відстані, що їх розділяють.
Для кожного вузла призначення:
- Якщо значення в зведеній частині плюс крайове значення, що з’єднує його, складає менше значення цільового вузла, оновіть його значення, оскільки знайдено новий коротший шлях.
- Якщо всі маршрути до цього вузла призначення вивчені, його можна перекреслити.
Крок 3:
Повторюйте крок 2, поки всі вузли не будуть перекреслені. Тепер у нас є графік, де значення, що зберігаються в будь-якому вузлі, будуть найменшою відстанню до нього від початкового вузла.
Більше інформації:
Детальніше про алгоритм Дейкстри
Інші алгоритми найкоротшого шляху