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

Читайте іншими мовами: English, 한국어, 日本語, 简体中文, 繁體中文, Українська, Español, Français, Deutsch, עברית

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

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

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

Практичні застосування алгоритму Дейкстри

GPS / навігаційні системи
Оптимізація маршрутів громадського транспорту та авіаліній
Інтернет-маршрутизація (протоколи OSPF, IS-IS)
Оптимізація мережевого трафіку та затримок
Пошук шляху в іграх (найкоротший шлях на карті)
Оптимізація маршрутів доставки
Проєктування логістичних та транспортних мереж

Покроковий приклад алгоритму Дейкстри

Припустімо, ми маємо зважений граф вершин, де кожне ребро має певну довжину. Наприклад, відстань між вершинами A і B становить 7 метрів (або просто 7m).

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

Початкова вершина, за визначенням, має відстань 0m від самої себе. З неї й починається пошук — вона єдина в черзі на початку.

Решта вершин додаються до черги з пріоритетом пізніше, у процесі обходу графа (під час відвідування сусідів).

Кожен сусід витягнутої з черги вершини перевіряється для обчислення відстані до нього від початкової вершини. Наприклад, відстань від A до B — це 0m + 7m = 7m.

Щоразу, коли ми відвідуємо нового (ще не баченого) сусіда, ми додаємо його в чергу з пріоритетом, де пріоритет — це відстань до цієї вершини від початкової.

Вершину B додаємо до мінімальної черги з пріоритетом, щоб відвідати її пізніше.

Відвідуємо наступного сусіда C вершини A. Відстань від A до C становить 0m + 9m = 9m.

Додаємо вершину C до мінімальної черги з пріоритетом.

Те саме робимо для вершини F. Поточна відстань від A до F — 0m + 14m = 14m.

Вершину F додаємо до черги для подальшого обходу.

Коли всі сусіди поточної вершини перевірені, ми додаємо її до множини visited. Такі вершини більше не відвідуємо.

Тепер вибираємо з черги наступну вершину, найближчу до початкової, і починаємо відвідувати її сусідів.

Якщо вершина, яку ми відвідуємо (наприклад, C), уже є в черзі, це означає, що відстань до неї вже обчислювалася раніше з іншого шляху (A → C). Якщо нова відстань (через інший шлях, наприклад A → B → C) менша, ми оновлюємо її в черзі. Якщо більша — залишаємо без змін.

Під час відвідування C через B (A → B → C), відстань дорівнює 7m + 10m = 17m. Це більше, ніж уже відома 9m для шляху A → C. Тож ми ігноруємо довший шлях.

Відвідуємо іншого сусіда B — вершину D. Відстань до D дорівнює 7m + 15m = 22m. Оскільки D ще не відвідано і її немає в черзі, додаємо її з пріоритетом 22m.

Тепер усіх сусідів B відвідано, тож додаємо B до множини visited. Наступною вибираємо вершину, що найближча до початкової.

Відвідуємо непереглянутих сусідів вершини C. Відстань до вершини F через C (A → C → F) дорівнює 9m + 2m = 11m. Це коротше за попередній шлях A → F довжиною 14m. Тому оновлюємо відстань до F — з 14m до 11m. Ми щойно знайшли коротший шлях.