Алгоритм Дейкстри
Знаходить найдешевший шлях від старту до цілі. Завжди бере найдешевше місце з черги з пріоритетом, тож вартість розтікається від старту, як вода.
- час O((V + E) log V)
- пам'ять O(V)
- використовує чергу з пріоритетом
Що це означає?
- Вартість: скільки коштує хід. У лабіринті земля коштує 1, бруд 3, вода 9; у графі — число на ребрі.
- Черга з пріоритетом: черга, де першим іде найдешевший, а не той, хто прийшов першим.
- Оцінка (h): припущення про вартість, що лишилася. A* лишається точним, лише якщо оцінка ніколи не завищена.
- Релаксація ребра: перевірка, чи шлях через поточне місце дає сусідові меншу вартість, і якщо так — її прийняття.
- у черзі
- поточна
- готова
- найдешевший шлях
- земля · 1
- бруд · 3
- вода · 9
- стіна
Нова: Старт у A1 з вартістю 0. Він єдиний у черзі.
Пробіл: відтворення або пауза. Стрілки ліворуч і праворуч: крок. Home і End: на початок або в кінець.
Спробуйте: Виберіть болото. Найдешевший шлях обходить увесь бруд: удвічі більше ходів, ніж по прямій, і все ж дешевше (34 проти 36).
Як це працює
Кожне місце отримує вартість: старт 0, решта нескінченність. Дейкстра тримає досягнуті місця в черзі з пріоритетом і завжди бере найдешевше. Його вартість тоді остаточна: будь-який інший шлях туди йшов би через щось не менш дороге. Потім він дивиться на сусідів: якщо шлях через щойно взяте місце дешевший за поточну вартість сусіда, сусід отримує нову вартість і запам’ятовує, звідки прийшов. Коли ціль взято, ці посилання ведуть назад найдешевшим шляхом.
Коли варто використовувати
Дейкстра потрібен, коли ходи коштують по-різному і жоден не коштує менше нуля: дорожні карти й навігатори, маршрутизація в мережах, найдешевша пересадка між рейсами. Якщо кожен хід коштує однаково, BFS дасть ту саму відповідь простіше. З від’ємними вартостями Дейкстра може помилитися; для них є Беллман–Форд.