Дейкстра и A* (кратчайший путь)

Содержание и основные понятия

← Вернуться к оглавлению
Alterna · глава 18 · страница 18.3
Дейкстра и A* (кратчайший путь)
Алгоритм Дейкстры и A* с эвристикой. Пошаговая визуализация.
Дейкстра — алгоритм кратчайшего пути от одной вершины до всех остальных. A* = Дейкстра + эвристика. Оба используются в навигаторах, играх, сетевой маршрутизации.
ФГОС
ФОП
ЕГЭ №1
01
Алгоритм Дейкстры
Всем вершинам присвоить dist[v] = ∞, кроме start: dist[start] = 0.
Поместить start в очередь с приоритетом (по dist).
Извлечь вершину u с минимальным dist. Пометить как обработанную.
Для каждого соседа v: если dist[u] + w(u,v) < dist[v], обновить dist[v] и prev[v] = u.
Повторять 3-4, пока очередь не пуста.
Сложность:
O((V+E)·log V) с приоритетной очередью.
02
A* — Дейкстра + эвристика
A* использует оценку
f(v) = g(v) + h(v)
, где g(v) — реальная стоимость пути от старта до v, h(v) — эвристика (оценка расстояния от v до цели).
Популярные эвристики:
Манхэттен
— сумма разностей координат (для сетки).
Евклидова
— расстояние по прямой.
Чебышёва
— max разностей.
Если h(v) допустима (никогда не переоценивает), A* находит оптимальный путь.
03
Визуализатор Дейкстры
Запусти — увидишь, как алгоритм проходит по графу
📍
Дейкстра пошагово