В основе алгоритма лежит жадно-динамический подход. "Жадный" — потому что на каждом шаге он выбирает локально оптимальную вершину (с минимальным известным расстоянием), "динамический" — потому что постоянно обновляет оценки расстояний до других вершин. Представим граф как набор городов (вершины), соединенных дорогами (ребра) с указанием расстояний (весов). Нам известен город старта, и нужно найти кратчайшие расстояния от него до всех остальных.
Пошаговая реализация алгоритма выглядит следующим образом. На вход подаются: граф (обычно в виде списка смежности или матрицы), начальная вершина `start`. На выходе我们需要 получить массив `dist[]`, где для каждой вершины `v` будет храниться длина кратчайшего пути от `start` до `v`, и, опционально, массив `prev[]` для восстановления самого пути.
Шаг 1: Инициализация. Создаем массив `dist[]` и заполняем его "бесконечностью" (очень большим числом), кроме вершины `start`, для которой `dist[start] = 0`. Создаем множество или очередь приоритетов `Q`, куда помещаем все вершины графа. Массив `prev[]` можно инициализировать значениями `null` или `-1`.
Шаг 2: Основной цикл. Пока `Q` не пусто, выполняем следующее. Из множества `Q` извлекаем вершину `u` с минимальным значением `dist[u]`. На первой итерации это будет вершина `start` с расстоянием 0. Эта вершина теперь считается "обработанной" — кратчайшее расстояние до нее найдено окончательно.
Шаг 3: Релаксация ребер. Для каждой соседней вершины `v`, смежной с `u` (т.е. для каждого ребра `u -> v` с весом `weight`), выполняем проверку: если `dist[u] + weight < dist[v]`, то мы нашли более короткий путь до `v` через `u`. В этом случае обновляем: `dist[v] = dist[u] + weight` и `prev[v] = u` (чтобы запомнить, откуда мы пришли). Если используется очередь с приоритетами, необходимо также обновить приоритет вершины `v` в очереди.
Шаг 4: Завершение. Когда все вершины извлечены из `Q` (или, в некоторых реализациях, когда обработаны все вершины), алгоритм завершается. Массив `dist[]` содержит итоговые кратчайшие расстояния.
Рассмотрим простой пример на графе из 4 вершин (A, B, C, D). Стартовая вершина — A. Ребра: A-B=6, A-C=2, C-B=3, B-D=1, C-D=5. Инициализация: dist[A]=0, dist[B]=dist[C]=dist[D]=∞. Q={A,B,C,D}.
- Извлекаем A (dist=0). Релаксируем ребра: для B: 0+6=6 < ∞ -> dist[B]=6, prev[B]=A. Для C: 0+2=2 < ∞ -> dist[C]=2, prev[C]=A.
- Извлекаем C (dist=2, минимальное). Релаксируем ребра из C: для B: 2+3=5 < 6 -> dist[B]=5, prev[B]=C. Для D: 2+5=7 < ∞ -> dist[D]=7, prev[D]=C.
- Извлекаем B (dist=5). Релаксируем ребро из B: для D: 5+1=6 < 7 -> dist[D]=6, prev[D]=B.
- Извлекаем D (dist=6). Соседей нет. Q пусто. Результат: dist[A]=0, dist[B]=5, dist[C]=2, dist[D]=6.
Ключевые аспекты для разработчиков. Структура данных: использование наивного массива для поиска минимума дает сложность O(V^2), что приемлемо для плотных графов. Для разреженных графов оптимальна очередь с приоритетом (обычно на основе двоичной кучи), которая снижает сложность до O((V+E) log V). В языках типа Python используется `heapq`, в Java — `PriorityQueue`.
Важнейшее ограничение: алгоритм Дейкстры не работает с отрицательными весами ребер. При их наличии может сработать алгоритм Беллмана-Форда. Отрицательный цикл в графе делает задачу нахождения кратчайшего пути не имеющей смысла.
Алгоритм находит широчайшее применение: маршрутизация в сетях (протоколы типа OSPF), навигационные системы (Google Maps), планирование задач, анализ социальных графов. Его вариации лежат в основе более сложных алгоритмов, таких как A* (A-star) для поиска пути с эвристикой.
Понимание Дейкстры — это не только знание шагов, но и глубокое осознание принципа оптимальности Беллмана: если кратчайший путь из A в C проходит через B, то его отрезок от A до B также является кратчайшим путем. Именно этот принцип позволяет алгоритму быть "жадным" и при этом всегда находить глобально оптимальное решение.
Комментарии (9)