Алгоритм Дейкстры

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

Поиск оптимальных маршрутов на примере данного графа

---

Основная идея

Алгоритм постепенно строит множество вершин, для которых уже найден кратчайший путь от начальной вершины. На каждом шаге он выбирает ту вершину, путь до которой минимален из всех ещё не обработанных, и "расслабляет" (обновляет) длины путей к её соседям, если нашёл более короткий путь.

---

Пошаговое описание

1. Задать начальную вершину s и установить расстояние до неё как 0: d[s] = 0.
2. Для всех остальных вершин v ≠ s задать d[v] = ∞.
3. Создать множество непосещённых вершин Q, содержащее все вершины графа.
4. Пока множество Q не пусто:
   • выбрать вершину u с минимальным d[u] из Q;
   • удалить u из Q;
   • для каждой соседней вершины v проверить: если путь через u короче текущего d[v], то обновить d[v] = d[u] + w(u, v), где w(u, v) — вес ребра.

---

Время работы

• При использовании обычной очереди с массивами: O(V²) (где V — количество вершин).
• При использовании очереди с приоритетом (например, кучи): O((V + E) log V), где E — количество рёбер.
• Это делает алгоритм эффективным даже для больших графов с малым числом рёбер (разреженных графов).

---

Пример

Пусть есть вершины A, B, C, D, E с рёбрами и весами:

• A → B (1), A → C (4), B → C (2), B → D (5), C → D (1), D → E (3)

Алгоритм найдет кратчайшие расстояния от A до всех остальных:

• A: 0
• B: 1
• C: 3
• D: 4
• E: 7

---

Ограничения

• Алгоритм не работает, если в графе есть рёбра с отрицательными весами. В таких случаях применяют, например, алгоритм Беллмана — Форда.
• Для поиска кратчайшего пути между всеми парами вершин можно использовать алгоритм Флойда — Уоршелла.