Принцип алгоритма Дейкстры
Алгоритм Дейкстры (Dijkstra\'s algorithm) — классический метод поиска кратчайшего пути от одной (стартовой) вершины ко всем остальным в графе. Разработан Эдсгером Дейкстрой в 1956 г.
Основная идея: жадно расширять «фронт» уже обработанных вершин, всегда выбирая следующую вершину с минимальным текущим расстоянием. Гарантирует оптимальное решение для графов с положительными весами.
Псевдокод
function Dijkstra(Graph, start): dist[start] = 0 for each vertex v in Graph: if v != start: dist[v] = ∞ prev[v] = undefined Q.add_with_priority(v, dist[v]) while Q is not empty: u = Q.extract_min() for each neighbor v of u: alt = dist[u] + length(u, v) if alt < dist[v]: dist[v] = alt prev[v] = u Q.decrease_priority(v, alt) return dist[], prev[]
Сложность Дейкстры
- Простая (массив): O(V²), где V — число вершин. Хороша для плотных графов (E ≈ V²).
- Двоичная куча: O((V + E) log V). Лучше для разрежённых графов (E << V²).
- Фибоначчиева куча: O(E + V log V). Теоретически быстрее, но константы большие.
Сравнение с другими алгоритмами
| Алгоритм | Сложность | Веса | Применение |
|---|---|---|---|
| Дейкстра | O(V²) | только + | маршрутизация |
| Беллман-Форд | O(V·E) | + и − | отрицательные веса |
| A* | O(b^d) | + | GPS, игры |
| Флойд-Уоршелл | O(V³) | + и − | все пары вершин |
| BFS | O(V+E) | без весов | кратчайший по рёбрам |
- Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms (CLRS), 4th ed.. CLRS. 2022.
- Dijkstra E.W. — A note on two problems in connexion with graphs. E.W. Dijkstra. 1959.
- Sedgewick R. — Algorithms 4th edition. Robert Sedgewick. 2011.
