Алгоритм Дейкстры
Последнее обновление
Алгоритм Дейкстры находит кратчайший путь от исходной вершины до всех остальных вершин графа с неотрицательными весами рёбер. Он хранит предварительное расстояние для каждой вершины, многократно фиксирует незафиксированную вершину с наименьшим предварительным расстоянием и релаксирует её рёбра, обновляя расстояние соседа всякий раз, когда находится более короткий маршрут через текущую вершину. Нажмите «воспроизвести» выше, чтобы увидеть, как расстояния уменьшаются по мере фиксации каждой вершины.
Ключевая идея жадная: как только выбрана ближайшая незафиксированная вершина, её расстояние окончательно, потому что любой другой маршрут к ней должен был бы пройти через вершину, которая уже дальше. С очередью с приоритетом на двоичной куче Дейкстра работает за время O((V + E) log V). Он требует неотрицательных весов — используйте Беллмана-Форда, если рёбра могут быть отрицательными.
Временная и пространственная сложность
| Реализация | Сложность | Примечания |
|---|---|---|
| Двоичная куча | O((V + E) log V) | Обычный практичный выбор |
| Просмотр массива | O(V²) | Проще; подходит для плотных графов |
| Память | O(V) | Расстояния + очередь с приоритетом |
| Требует | Неотрицательные веса | Отрицательные рёбра ломают жадный выбор |
Пошагово
| Шаг | Что происходит |
|---|---|
| 1 | Установите расстояние источника в 0, а все остальные — в бесконечность. |
| 2 | Выберите незафиксированную вершину с наименьшим предварительным расстоянием. |
| 3 | Отметьте её как зафиксированную — её кратчайшее расстояние теперь окончательно. |
| 4 | Для каждого соседа вычислите расстояние-через-текущую + вес ребра. |
| 5 | Если оно меньше текущего расстояния соседа, релаксируйте его. |
| 6 | Повторяйте, пока все достижимые вершины не будут зафиксированы. |
Разобранный пример
Кратчайшие пути от источника A в графе с рёбрами A-B=4, A-C=1, C-B=2, C-D=5, B-D=1:
| Шаг | Фиксация | Расстояния | Действие |
|---|---|---|---|
| 0 | - | A=0, B=∞, C=∞, D=∞ | Инициализация: источник A=0, все остальные — бесконечность. |
| 1 | A (0) | B=4, C=1, D=∞ | Релаксируем рёбра из A: устанавливаем B=4, C=1. |
| 2 | C (1) | B=3, D=6 | Через C: B=1+2=3 лучше 4; D=1+5=6. |
| 3 | B (3) | D=4 | Через B: D=3+1=4 лучше 6. |
| 4 | D (4) | A=0, C=1, B=3, D=4 | Фиксируем D; релаксировать больше нечего. Готово. |
Когда использовать алгоритм Дейкстры
| Используйте, когда | Избегайте, когда |
|---|---|
| Все веса рёбер неотрицательны | Любое ребро может быть отрицательным — используйте Беллмана-Форда |
| Нужны кратчайшие пути от одного источника ко всем вершинам | Нужны кратчайшие пути между всеми парами — Флойд-Уоршелл проще |
| Граф взвешенный и нужны точные расстояния | Граф невзвешенный — простой BFS быстрее и проще |
| У вас есть хорошая куча или очередь с приоритетом | Нужно быстро достичь одной цели с эвристикой — используйте A* |
Код Dijkstra's Algorithm
Чистая, готовая к запуску реализация Dijkstra's Algorithm на Python, JavaScript, Java, C++, C. Выберите язык, скопируйте код или откройте его уже загруженным в плейграунде Coddy.
Код Dijkstra's Algorithm на Python
Python
1import heapq2
3
4def dijkstra(graph, start):5 dist = {node: float("inf") for node in graph}6 dist[start] = 07 pq = [(0, start)]8 while pq:9 d, node = heapq.heappop(pq)10 if d > dist[node]:11 continue # stale entry, a shorter path was already found12 for neighbor, weight in graph[node]:13 new_dist = d + weight14 if new_dist < dist[neighbor]:15 dist[neighbor] = new_dist16 heapq.heappush(pq, (new_dist, neighbor))17 return dist18
19
20graph = {21 "A": [("B", 4), ("C", 1)],22 "B": [("D", 1)],23 "C": [("B", 2), ("D", 5)],24 "D": [("E", 3)],25 "E": [],26}27
28for node, d in dijkstra(graph, "A").items():29 print(f"A -> {node}: {d}")Код Dijkstra's Algorithm на JavaScript
JavaScript
1const graph = {2 A: { B: 4, C: 2 },3 B: { C: 5, D: 10 },4 C: { E: 3 },5 D: { F: 11 },6 E: { D: 4 },7 F: {},8};9
10function dijkstra(source) {11 const dist = {};12 const visited = new Set();13 for (const node in graph) dist[node] = Infinity;14 dist[source] = 0;15 while (visited.size < Object.keys(graph).length) {16 // JS has no built-in heap: linear scan for the closest node (O(V^2))17 let u = null;18 for (const node in dist) {19 if (!visited.has(node) && (u === null || dist[node] < dist[u])) {20 u = node;21 }22 }23 if (dist[u] === Infinity) break;24 visited.add(u);25 for (const [v, w] of Object.entries(graph[u])) {26 if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;27 }28 }29 return dist;30}31
32console.log("Shortest distances from A:", dijkstra("A"));Код Dijkstra's Algorithm на Java
Java
1import java.util.ArrayList;2import java.util.Arrays;3import java.util.List;4import java.util.PriorityQueue;5
6public class Main {7 public static void main(String[] args) {8 int n = 6;9 List<List<int[]>> adj = new ArrayList<>();10 for (int i = 0; i < n; i++) adj.add(new ArrayList<>());11 int[][] edges = {12 {0, 1, 4}, {0, 2, 1}, {2, 1, 2}, {1, 3, 5},13 {2, 3, 8}, {3, 4, 3}, {2, 5, 10}, {4, 5, 2}14 };15 for (int[] e : edges) {16 adj.get(e[0]).add(new int[]{e[1], e[2]});17 adj.get(e[1]).add(new int[]{e[0], e[2]});18 }19
20 int[] dist = new int[n];21 Arrays.fill(dist, Integer.MAX_VALUE);22 dist[0] = 0;23 PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);24 pq.add(new int[]{0, 0}); // {node, distance}25 while (!pq.isEmpty()) {26 int[] cur = pq.poll();27 int node = cur[0], d = cur[1];28 if (d > dist[node]) continue; // stale queue entry29 for (int[] edge : adj.get(node)) {30 int next = edge[0], nd = d + edge[1];31 if (nd < dist[next]) {32 dist[next] = nd;33 pq.add(new int[]{next, nd});34 }35 }36 }37 System.out.println("Shortest distances from 0: " + Arrays.toString(dist));38 }39}Код Dijkstra's Algorithm на C++
C++
1#include <iostream>2#include <queue>3#include <vector>4
5int main() {6 const int INF = 1000000000;7 // Weighted directed graph: adj[u] = {(neighbor, weight), ...}8 std::vector<std::vector<std::pair<int, int>>> adj = {9 {{1, 4}, {2, 1}}, // 010 {{3, 1}}, // 111 {{1, 2}, {3, 5}}, // 212 {{4, 3}}, // 313 {}, // 414 };15 int n = static_cast<int>(adj.size());16 std::vector<int> dist(n, INF);17 dist[0] = 0;18 using State = std::pair<int, int>; // (distance, node)19 std::priority_queue<State, std::vector<State>, std::greater<State>> pq;20 pq.push({0, 0});21 while (!pq.empty()) {22 auto [d, u] = pq.top();23 pq.pop();24 if (d > dist[u]) continue; // stale queue entry25 for (auto [v, w] : adj[u]) {26 if (d + w < dist[v]) {27 dist[v] = d + w;28 pq.push({dist[v], v});29 }30 }31 }32 for (int v = 0; v < n; ++v) {33 std::cout << "Distance 0 -> " << v << ": " << dist[v] << "\n";34 }35 return 0;36}Код Dijkstra's Algorithm на C
C
1#include <stdbool.h>2#include <stdio.h>3
4#define N 55#define INF 10000000006
7int main(void) {8 // Weighted directed graph: w[u][v] = 0 means no edge9 int w[N][N] = {10 {0, 4, 1, 0, 0},11 {0, 0, 0, 1, 0},12 {0, 2, 0, 5, 0},13 {0, 0, 0, 0, 3},14 {0, 0, 0, 0, 0},15 };16 int dist[N];17 bool done[N] = {false};18 for (int v = 0; v < N; v++) dist[v] = INF;19 dist[0] = 0;20 // O(V^2) scan for the closest unfinished node (no heap needed here)21 for (int iter = 0; iter < N; iter++) {22 int u = -1;23 for (int v = 0; v < N; v++) {24 if (!done[v] && (u == -1 || dist[v] < dist[u])) u = v;25 }26 if (dist[u] == INF) break; // remaining nodes are unreachable27 done[u] = true;28 for (int v = 0; v < N; v++) {29 if (w[u][v] > 0 && dist[u] + w[u][v] < dist[v]) {30 dist[v] = dist[u] + w[u][v];31 }32 }33 }34 for (int v = 0; v < N; v++) {35 printf("Distance 0 -> %d: %d\n", v, dist[v]);36 }37 return 0;38}Часто задаваемые вопросы об алгоритме Дейкстры
Какова временная сложность алгоритма Дейкстры?
С очередью с приоритетом на двоичной куче он работает за
O((V + E) log V). Простая версия, которая на каждом шаге просматривает массив в поиске минимума, имеет сложность O(V²), что на плотных графах может оказаться даже быстрее. Обе используют память O(V).Почему Дейкстра не работает с отрицательными весами рёбер?
Дейкстра предполагает, что как только зафиксирована ближайшая незафиксированная вершина, это расстояние окончательно. Отрицательное ребро могло бы позже создать более короткий путь к уже зафиксированной вершине, нарушив это предположение. Для графов с отрицательными весами используйте алгоритм Беллмана-Форда.
В чём разница между Дейкстрой и BFS?
BFS находит кратчайшие пути, считая рёбра (вес каждого ребра фактически равен 1), используя обычную очередь. Дейкстра обобщает это на взвешенные графы, всегда расширяя вершину с наименьшим суммарным расстоянием с помощью очереди с приоритетом. На невзвешенном графе оба дают одни и те же пути.
В чём разница между Дейкстрой и поиском A*?
A* — это Дейкстра плюс эвристика, которая оценивает оставшееся расстояние до цели, поэтому она направляет поиск к этой цели вместо равномерного расширения во все стороны. Когда эвристика равна нулю, A* вырождается ровно в Дейкстру. Используйте A*, когда у вас одна цель и хорошая допустимая эвристика; используйте Дейкстру, когда нужны расстояния до всех вершин.
Когда использовать Дейкстру вместо Беллмана-Форда?
Используйте Дейкстру всякий раз, когда все веса рёбер неотрицательны — она быстрее:
O((V + E) log V) против O(V·E) у Беллмана-Форда. Выбирайте Беллмана-Форда только тогда, когда рёбра могут быть отрицательными или нужно обнаруживать отрицательные циклы. На неотрицательных графах Дейкстра почти всегда лучший выбор.Может ли Дейкстра снова посетить вершину после её фиксации?
Нет — как только вершина зафиксирована, её расстояние окончательно и она больше никогда не релаксируется. Частая ошибка в реализациях на куче — оставлять устаревшие записи в очереди с приоритетом после того, как расстояние вершины улучшилось; нужно пропускать извлечённую вершину, если она уже зафиксирована (её извлечённое расстояние превышает записанное). Пропуск этой проверки всё равно даёт правильные ответы, но тратит лишнюю работу.
Связанные ресурсы
Больше визуализаций
