Кратчайший путь — алгоритм Дейкстры

ОБЯЗАТЕЛЬНОДЛЯ НОВИЧКОВ

Разработчику Инженеру

---

Постановка задачи

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

Примеры: маршрут в навигаторе, задержки в сети, стоимость перевозки между складами.

Алгоритм Дейкстры (Эдсгер Дейкстра, 1956) — жадный метод: на каждом шаге «закрепляется» ближайшая ещё не обработанная вершина, и через неё релаксируются (улучшаются) расстояния до соседей.

Ограничение по весам

При отрицательных весах рёбер Дейкстра может дать неверный ответ. Для таких графов используют другие алгоритмы (например, Беллмана–Форда). Перед применением проверьте предусловия — см. раздел про корректный ввод в поиске.

---

Идея релаксации

Для каждой вершины v храним текущую оценку расстояния dist[v]. Изначально dist[s] = 0, остальным — «бесконечность».

Релаксация ребра (u → v) с весом w:

если dist[u] + w < dist[v] то
  dist[v] := dist[u] + w
  предок[v] := u
конец если

Когда вершина u с минимальным dist среди непосещённых обработана, её расстояние уже окончательное (при неотрицательных весах).

---

Псевдокод

АЛГОРИТМ ДЕЙКСТРА(G, s)
  для каждой вершины v
    dist[v] := +∞
    предок[v] := пусто
  конец для
  dist[s] := 0
  Q := приоритетная очередь всех вершин по dist
  пока Q не пуста
    u := извлечь из Q вершину с минимальным dist
    для каждого ребра (u → v) с весом w
      если dist[u] + w < dist[v]
        dist[v] := dist[u] + w
        предок[v] := u
        обновить позицию v в Q
      конец если
    конец для
  конец пока
  вернуть dist, предок
КОНЕЦ

Восстановление пути до t: идти от t по цепочке предок до s и развернуть список.

---

Сложность

Реализация очереди	Время
Линейный поиск минимума	O(V²)
Двоичная куча (приоритетная очередь)	O((V + E) log V)

V — число вершин, E — число рёбер. Память — O(V) для массивов dist и предок.

---

Сравнение с BFS

	BFS	Дейкстра
Веса рёбер	Все равны 1 (или нет весов)	Неотрицательные числа
Результат	Кратчайшее число шагов	Минимальная сумма весов
Типичная сложность	O(V + E)	O((V + E) log V) с кучей

---

Практика

• Навигаторы и логистика — кратчайший путь с учётом длины или времени.
• Маршрутизация в сетях — метрика задержки на канале.
• Игровой AI — стоимость клеток на карте с препятствиями.

Жадность и оптимум

Дейкстра — пример жадного алгоритма: локально выбирается ближайшая вершина, и при неотрицательных весах это даёт глобально кратчайшие пути. Жадность без доказательства может подвести в других задачах — см. графы и задачу коммивояжёра в тренировке мышления.

---

Связанные материалы

• Графы — определения и BFS/DFS
• PageRank — другая задача на том же веб-графе
• Математическое программирование — сетевые модели пути