💻 Алгоритми · Інформатика
📅 Березень 2026⏱ 11 хв🟢 Початковий
·
Останнє оновлення: 23 червня 2026 р.
Дейкстра та A*: алгоритми пошуку найкоротшого шляху
Пошук найкоротшого шляху між двома точками — одна з найбільш практично корисних задач інформатики. Едсгер Дейкстра розв'язав її у 1956 році. Через кілька десятиліть A* зробив цей пошук швидшим завдяки просторовій інтуїції. Разом вони лежать в основі GPS-навігації, ігрового ШІ, планування руху роботів і маршрутизації мереж.
1. Графи: вершини, ребра та ваги
Граф G = (V, E) складається з вершин (вузлів) V і ребер E. У зваженому орієнтованому графі кожне ребро (u, v) має невід'ємну вартість w(u,v) ≥ 0, яка відповідає відстані, часу чи певному штрафу. Задача найкоротшого шляху: знайти шлях мінімальної вартості від джерела s до будь-якого або до всіх пунктів призначення.
- Найкоротший шлях з одного джерела (SSSP): знайти найкоротші шляхи від одного джерела до всіх інших вершин. Розв'язується алгоритмами Дейкстри та Беллмана–Форда.
- Найкоротший шлях між парою вершин: від s до t. Для цього оптимізований A*.
- Найкоротші шляхи між усіма парами (APSP): між усіма парами вершин. Флойд–Воршелл: O(V³).
Релаксація (ключова операція):
If d[v] > d[u] + w(u,v):
d[v] = d[u] + w(u,v)
parent[v] = u
d[v] = поточна найкраща відома відстань від джерела до v
Спочатку: d[s] = 0, d[v] = ∞ для всіх інших v
2. Алгоритм Дейкстри
Дейкстра (1959) обробляє вершини в порядку їхньої попередньої найкоротшої відстані, використовуючи чергу з пріоритетами:
Алгоритм Дейкстри:
DIJKSTRA(G, w, s):
d[s] = 0; d[v] = ∞ для v ≠ s
Q = мін-черга з пріоритетами з усіма вершинами за ключем d[v]
поки Q не порожня:
u = EXTRACT-MIN(Q) # вершина з найменшим d[u]
для кожного сусіда v вершини u:
якщо d[u] + w(u,v) < d[v]:
d[v] = d[u] + w(u,v) # релаксація
parent[v] = u
DECREASE-KEY(Q, v, d[v])
Доведення коректності (неформальне):
Коли u вилучається з Q, d[u] є ОСТАТОЧНИМ (не може бути покращене).
Доведення: якби існував коротший шлях, він проходив би через якусь
необроблену вершину x з d[x] ≥ d[u] → загальний шлях ≥ d[u].
Отже, d[u] оптимальне на момент вилучення.
Що й треба було довести. (Потрібні невід'ємні ваги ребер!)
Дейкстра на від'ємних вагах: алгоритм Дейкстри не працює з ребрами від'ємної ваги, бо припущення жадібного вилучення порушується. Натомість використовуйте Беллмана–Форда: складність O(VE), обробляє від'ємні ваги та виявляє від'ємні цикли. Корисний у виявленні фінансового арбітражу та протоколах маршрутизації на кшталт OSPF (який використовує Дейкстру в мережах з додатними вартостями каналів).
3. Складність і структури даних
Складність Дейкстри залежить від реалізації черги з пріоритетами:
┌───────────────────────┬────────────┬────────────────────────────┐
│ Черга з пріоритетами │ Час загалом│ Найкраще для │
├───────────────────────┼────────────┼────────────────────────────┤
│ Масив (несортований) │ O(V²) │ Щільні графи (E ≈ V²) │
│ Двійкова купа │ O((V+E) log V) │ Розріджені графи │
│ Купа Фібоначчі │ O(E + V log V) │ Теоретичний оптимум │
└───────────────────────┴────────────┴────────────────────────────┘
Типова дорожня мережа (OpenStreetMap, Лондон):
V ≈ 1 000 000 вузлів, E ≈ 2 500 000 ребер (розріджена)
Дейкстра на двійковій купі: ~50–100 мс на сучасному ЦП для SSSP
Просторова складність: O(V + E)
4. Пошук A* та евристики
A* (Харт, Нільссон, Рафаель, 1968) удосконалює Дейкстру, спрямовуючи пошук до цілі за допомогою евристики h(v) — оцінки залишкової вартості від v до цілі t:
Оцінювальна функція A*:
f(v) = g(v) + h(v)
g(v) = точна вартість від джерела s до v (так само як d[v] у Дейкстри)
h(v) = евристична оцінка вартості від v до цілі t
Алгоритм A*:
Те саме, що Дейкстра, але чергу з пріоритетами впорядковано за f(v) = g(v) + h(v)
замість лише g(v).
EXTRACT-MIN повертає вершину з найменшим f = g + h.
Типові евристики для геометричних графів:
Евклідова відстань: h(v) = √((x_v−x_t)² + (y_v−y_t)²)
Манхеттенська відстань: h(v) = |x_v−x_t| + |y_v−y_t| (графи-ґратки)
Відстань Гаверсина: відстань по великому колу на сфері (координати GPS)
Чому h допомагає:
Дейкстра досліджує концентричними колами навколо джерела.
A* досліджує еліпс у напрямку цілі → менше розгорнутих вузлів.
Прискорення на дорожніх мережах: у 5–100× менше оброблених вузлів, ніж у Дейкстри.
5. Допустимість і узгодженість
Допустимість (гарантія оптимальності):
h(v) ≤ h*(v) для всіх v
h*(v) = справжня мінімальна вартість від v до цілі.
«Ніколи не переоцінювати» → A* усе одно знаходить оптимальний шлях.
Узгодженість (монотонність) — сильніша умова:
h(u) ≤ w(u,v) + h(v) (нерівність трикутника для h)
Якщо h узгоджена → g[v] остаточне при першому вилученні v
→ повторне вставлення не потрібне → чистіший алгоритм
Приклади:
Евклідова відстань: узгоджена ✓ (нерівність трикутника виконується в ℝⁿ)
Манхеттенська на ґратці: узгоджена ✓
«Завжди 0»: допустима ✓ → A* стає Дейкстрою
«Пряма відстань × 1.5»: НЕ допустима → може пропустити оптимальний шлях
Недопустимі евристики (напр., зважений A* з w > 1):
f = g + w·h, w = 1.5
Швидше, але довжина розв'язку ≤ (1+ε) × оптимальна
Застосовується в ігровому ШІ реального часу, де швидкість > точність
6. Варіанти алгоритму
- Двонапрямлений Дейкстра/A*: пошук одночасно від джерела й цілі. Зустрічаються посередині. Теоретичне прискорення: фронт пошуку зменшується вдвічі. Застосовується в картографічних додатках. Двонапрямлений A* вимагає обережності з умовою завершення.
- D* Lite: інкрементальне переплановування для роботів, що рухаються в частково відомих середовищах. Ефективно перераховує шлях при зміні карти — застосовується в навігації марсоходів.
- Jump Point Search (JPS): для ґраткових графів з однаковою вартістю JPS рекурсивно визначає «точки стрибка», відсікаючи величезну кількість проміжних вузлів. Прискорення у 10–100× порівняно з A* на ґратках без попередньої обробки.
- Стискальні ієрархії (Contraction Hierarchies, CH): офлайн попередня обробка додає ребра-«скорочення». Час запиту для маршруту 1000 км на європейській дорожній мережі: <1 мс проти ~50 мс у Дейкстри.
- Алгоритми на основі HLD (Highway Hierarchies): використовують спостереження, що довгі маршрути переважно проходять автомагістралями. Концептуальна основа багатьох промислових GPS-систем.
- Беллман–Форд: обробляє від'ємні ваги. O(VE). Лежить в основі протоколів маршрутизації OSPF/RIP та SPFA (Беллман–Форд, оптимізований чергою).
7. Практичні застосування
- GPS-навігація: Google Maps, Apple Maps і Waze використовують ретельно спроєктовані варіанти CH + Дейкстра, що оновлюються даними про трафік у реальному часі. Реальний дорожній граф континенту має ~100 млн вузлів. Попередня обробка може тривати хвилини; запити — мілісекунди.
- Пошук шляху в іграх: NPC та юніти в стратегіях реального часу використовують A* на навігаційних сітках (NavMesh) — на основі полігонів, а не ґраток. Ігри на кшталт StarCraft 2 виконують тисячі запитів A* на секунду. JPS популярний для ігор на основі ґраток.
- Маршрутизація мереж (OSPF): інтернет-маршрутизатори виконують Дейкстру над базою станів каналів, щоб обчислити таблиці маршрутизації. Кожен маршрутизатор має повну карту мережі; Дейкстра знаходить найкоротші шляхи до всіх інших маршрутизаторів.
- Робототехніка та автономний транспорт: ROS (Robot Operating System) використовує A* і Дейкстру через навігаційний стек `move_base`. Безпілотні автомобілі поєднують A* з модельно-прогностичним керуванням для планування траєкторій.
- Планування авіарейсів: пошук стикувань рейсів, перемаршрутизація з мінімальною вартістю при скасуваннях. Багатокритеріальний найкоротший шлях (час + вартість + пересадки).
Обчислювальна складність — контекст P проти NP: найкоротший шлях у графі належить до класу P (розв'язується за поліноміальний час). Найскладніша споріднена задача — задача комівояжера (TSP) — є NP-складною: знайти найкоротший гамільтонів цикл, що відвідує всі вузли. TSP вимагає відвідати кожну вершину рівно один раз; найкоротший шлях може повертатися до вершин. Ця тонка відмінність перетворює розв'язну задачу на таку, для якої немає відомого поліноміального розв'язку для великих вхідних даних.