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

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

История

Алгоритм был впервые сформулирован Эдсгером Дейкстрой в 1956 году, когда он работал над задачей поиска кратчайшего пути для демонстрации возможностей нового компьютера ARMAC. Первоначально алгоритм был реализован для графа с 64 вершинами. Дейкстра опубликовал описание алгоритма в 1959 году в статье «A note on two problems in connexion with graphs» (Заметка о двух задачах, связанных с графами). В этой работе он также предложил алгоритм для нахождения минимального остовного дерева, известный как алгоритм Прима.

В 1960-х годах алгоритм был адаптирован для использования в маршрутизации пакетов в компьютерных сетях, в частности, в протоколе OSPF (Open Shortest Path First). В 1970-х годах были разработаны различные модификации, позволяющие ускорить его работу за счёт использования приоритетных очередей.

Постановка задачи

Пусть задан взвешенный ориентированный или неориентированный граф G = (V, E), где V — множество вершин, E — множество рёбер. Каждому ребру e ∈ E приписан неотрицательный вес w(e) ≥ 0. Требуется найти кратчайшие расстояния от заданной вершины-источника s ∈ V до всех остальных вершин графа. Кратчайшим расстоянием называется минимальная сумма весов рёбер на пути от s до целевой вершины.

Описание алгоритма

Алгоритм Дейкстры работает следующим образом:

Инициализация: каждой вершине v присваивается начальное расстояние d[v], равное бесконечности для всех вершин, кроме источника s, для которого d[s] = 0. Создаётся множество непосещённых вершин Q.
Выбор текущей вершины: из множества Q выбирается вершина u с минимальным текущим расстоянием d[u]. Эта вершина считается «посещённой» и удаляется из Q.
Релаксация рёбер: для каждого соседа v вершины u, который ещё не посещён, вычисляется новое расстояние d[u] + w(u, v). Если это значение меньше текущего d[v], то d[v] обновляется.
Повторение: шаги 2–3 повторяются до тех пор, пока множество Q не станет пустым или пока не будут обработаны все достижимые вершины.

После завершения работы алгоритма массив d содержит кратчайшие расстояния от источника до всех вершин. Если вершина недостижима, её расстояние остаётся равным бесконечности.

Реализация

Наивная реализация

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

Реализация с приоритетной очередью

Для ускорения работы используется приоритетная очередь (например, бинарная куча или Фибоначчиева куча). В этом случае выбор вершины с минимальным расстоянием выполняется за O(log V), а релаксация рёбер — за O(log V) для каждого ребра. Общая временная сложность составляет O((V + E) log V), где E — количество рёбер. Для графов с большим количеством вершин и рёбер это значительно быстрее наивной реализации.

Псевдокод (с приоритетной очередью)

``` function Dijkstra(Graph, source): dist[source] = 0 for each vertex v in Graph: if v != source: dist[v] = INFINITY prev[v] = UNDEFINED Q.add(v, dist[v])

while Q is not empty: u = Q.extract_min() for each neighbor v of u: alt = dist[u] + weight(u, v) if alt < dist[v]: dist[v] = alt prev[v] = u Q.decrease_key(v, alt) return dist, prev ```

Свойства

Корректность

Алгоритм Дейкстры корректен для графов с неотрицательными весами рёбер. Доказательство основано на том, что после выбора вершины u с минимальным расстоянием, это расстояние является окончательным, так как любой другой путь к u будет проходить через вершину с большим или равным расстоянием. При наличии отрицательных весов алгоритм может давать неверные результаты, так как более короткий путь может быть найден после того, как вершина уже была посещена.

Ограничения

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

Применение

Компьютерные сети

Алгоритм Дейкстры является основой протокола маршрутизации OSPF (Open Shortest Path First), используемого в IP-сетях. В OSPF каждый маршрутизатор строит топологическую карту сети и вычисляет кратчайшие пути до всех остальных маршрутизаторов с помощью алгоритма Дейкстры. Веса рёбер могут задаваться администратором сети на основе пропускной способности, задержки или других метрик.

Транспортная логистика

В навигационных системах (например, Яндекс.Карты, Google Maps) алгоритм Дейкстры используется для поиска кратчайшего маршрута между точками на карте. Весами рёбер могут быть расстояние, время в пути, стоимость проезда или другие параметры. Для ускорения работы применяются эвристики, такие как алгоритм A* (A-star), являющийся модификацией алгоритма Дейкстры с использованием эвристической оценки расстояния до цели.

Геоинформационные системы

В ГИС алгоритм применяется для анализа сетей дорог, трубопроводов, линий электропередач. Он позволяет находить оптимальные маршруты, рассчитывать зоны доступности и выполнять другие задачи пространственного анализа.

Робототехника

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

Модификации

Алгоритм A*

Является расширением алгоритма Дейкстры, в котором используется эвристическая функция h(v), оценивающая расстояние от вершины v до цели. Выбор вершины осуществляется на основе суммы d[v] + h(v), что позволяет сократить количество просматриваемых вершин и ускорить поиск. Алгоритм A* гарантирует нахождение оптимального пути, если эвристика является допустимой (не переоценивает истинное расстояние).