Как работает алгоритм Дейкстры и какие у него ограничения?

Алгоритм Дейкстры находит кратчайшие пути от стартовой вершины во взвешенном графе с неотрицательными весами: жадно извлекает ближайшую непосещённую вершину и релаксирует её рёбра.

Как работает

1. dist[start] = 0, остальным — бесконечность; все вершины в приоритетной очереди.
2. Извлекаем вершину с минимальным dist и помечаем посещённой.
3. Для каждого ребра (u, v): если dist[u] + w < dist[v] — обновляем dist[v].

Сложность

• С бинарной кучей: O((V + E) log V).
• Наивно на массиве: O(V²) — приемлемо для плотных графов.

Ограничения

• Отрицательные веса ломают жадный выбор: зафиксированное расстояние может оказаться не минимальным — там нужен Беллман-Форд.
• Кратчайшие пути между всеми парами — Флойд-Уоршелл за O(V³).

Почему корректен

Извлекаемая вершина имеет минимальный dist среди непосещённых; любой обходной путь пошёл бы через вершину с не меньшим dist, а неотрицательные веса его только увеличат.

Коротко для собеседования

Дейкстра на каждом шаге фиксирует ближайшую необработанную вершину и через неё улучшает расстояния до соседей; с кучей это O((V + E) log V). Работает только без отрицательных весов, иначе берут Беллмана–Форда, а поиск к одной цели ускоряют эвристикой A*.