В основе алгоритма лежит жадный (greedy) подход. Мы последовательно исследуем наиболее перспективные вершины графа, постепенно находя кратчайшие расстояния до всех остальных от выбранной начальной вершины. Критически важное ограничение: веса всех рёбер должны быть неотрицательными. Наличие отрицательных весов ломает логику жадного выбора и требует использования других алгоритмов, например, Беллмана-Форда.
Для работы алгоритма нам необходимо поддерживать две ключевые структуры данных:
- Массив/словарь `dist`, хранящий текущее кратчайшее известное расстояние от начальной вершины до каждой другой. Изначально для стартовой вершины расстояние равно 0, для всех остальных — бесконечность (условно очень большое число).
- Множество (чаще всего приоритетная очередь — min-heap) непосещенных вершин, упорядоченное по текущему значению расстояния `dist`. Изначально там все вершины.
Выбираем начальную вершину (допустим, A). Устанавливаем dist[A] = 0. Для всех остальных вершин (B, C, D…) dist = ∞. Помещаем все вершины в приоритетную очередь, где приоритет — это текущее dist.
Шаг 2: Извлечение вершины с минимальным расстоянием.
Извлекаем из очереди вершину с наименьшим значением `dist`. На первой итерации это будет стартовая вершина A (с dist=0). Эта вершина теперь считается «обработанной» — кратчайший путь до нее найден окончательно.
Шаг 3: Релаксация рёбер (Relaxation).
Рассматриваем всех соседей извлеченной вершины (по исходящим рёбрам). Для каждого соседа вычисляем потенциально новый путь: `новое_расстояние = dist[текущей_вершины] + вес_ребра_к_соседу`.
Если это `новое_расстояние` меньше текущего значения `dist[соседа]`, то мы нашли более короткий путь! Мы обновляем: `dist[соседа] = новое_расстояние`. Также необходимо обновить приоритет этой вершины в очереди (или просто добавить новую запись, если очередь это поддерживает). Кроме того, полезно сохранять предшественника (`prev[соседа] = текущая_вершина`), чтобы потом восстановить не только длину, но и сам путь.
Шаг 4: Повторение.
Повторяем Шаги 2 и 3 до тех пор, пока приоритетная очередь не опустеет или пока мы не извлечем целевую вершину (если нам нужен путь только до одной конкретной). На каждой итерации мы окончательно фиксируем кратчайшее расстояние до одной новой вершины.
Давайте проиллюстрируем на простом графе из 4 вершин (A, B, C, D). Рёбра: A->B=4, A->C=2, B->D=3, C->B=1, C->D=5. Начало: A.
- Итерация 1: Извлекаем A (dist=0). Релаксируем: dist[B] = 4, dist[C] = 2. Очередь: C(2), B(4), D(∞).
- Итерация 2: Извлекаем C (dist=2). Релаксируем соседей: Для B: 2+1=3 < 4 → обновляем dist[B]=3. Для D: 2+5=7 → dist[D]=7. Очередь: B(3), D(7).
- Итерация 3: Извлекаем B (dist=3). Релаксируем соседа D: 3+3=6 < 7 → обновляем dist[D]=6. Очередь: D(6).
- Итерация 4: Извлекаем D (dist=6). Соседей нет. Очередь пуста.
С практической точки зрения, эффективность алгоритма зависит от выбора структур данных. Использование наивного массива для поиска минимума даст сложность O(V^2), что приемлемо для плотных графов. Однако для разреженных графов (как в большинстве реальных задач) использование двоичной кучи (min-heap) в качестве приоритетной очередь снижает сложность до O((V+E) log V), где V — число вершин, E — число рёбер. В языках программирования это реализуется через `PriorityQueue` в Java, `heapq` в Python или `std::priority_queue` в C++.
Понимание алгоритма Дейкстры открывает дорогу к более сложным концепциям: A* поиск (эвристическая оптимизация Дейкстры), способы работы с отрицательными весами и динамическими графами. Это не устаревающий инструмент, обязательный для арсенала любого разработчика, работающего с алгоритмами, графами или системами, где требуется оптимальное планирование маршрутов.
Комментарии (9)