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