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

1 Свойства и структура алгоритмов

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

Алгоритм Дейкстры предназначен для решения задачи поиска кратчайшего пути на графе. Для заданного ориентированного взвешенного графа с неотрицательными весами алгоритм находит кратчайшие расстояния от выделенной вершины-источника до всех остальных вершин графа. Алгоритм Дейкстры (с использованием фибоначчиевой кучи) выполняется за время $O(m + n \ln n)$ и является асимптотически быстрейшим из известных последовательных алгоритмов для данного класса задач.

1.2 Математическое описание

Пусть задан граф $G = (V, E)$ с весами рёбер $f(e)$ и выделенной вершиной-источником $u$. Обозначим через $d(v)$ кратчайшее расстояние от источника $u$ до вершины $v$.

Пусть уже вычислены все расстояния, не превосходящие некоторого числа $r$, то есть расстояния до вершин из множества $V_r = \{ v \in V \mid d(v) \le r \}$. Пусть

$(v, w) \in \arg\min \{ d(v) + f(e) \mid v \in V, e = (v, w) \in E \}.$

Тогда $d(w) = d(v) + f(e)$, и $v$ лежит на кратчайшем пути от $u$ к $w$.

Величины $d^+(w) = d(v) + f(e)$, где $v \in V_r$, $e = (v, w) \in E$, называются предполагаемыми расстояниями и являются оценкой сверху для настоящих расстояний: $d(w) \le d^+(w)$.

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

1.3 Вычислительное ядро алгоритма

Основные вычисления связаны с операциями над очередью с приоритетом:

• извлечение минимального элемента (delete_min);
• уменьшение приоритета элемента (decrease_key).

1.4 Макроструктура алгоритма

Псевдокод алгоритма:

Входные данные:
  граф с вершинами V, рёбрами E с весами f(e);
  вершина-источник u.
Выходные данные: расстояния d(v) до каждой вершины v ∈ V от вершины u.

Q := new priority queue
for each v ∈ V do
    if v = u then d(v) := 0 else d(v) := ∞ 
    Q.insert(v, d(v))

while Q ≠ ∅:
    v := Q.delete_min()
    for each e = (v, w) ∈ E:
        if d(w) > d(v) + f(e):
            d(w) := d(v) + f(e)
            Q.decrease_key(w, d(w))

1.6 Последовательная сложность алгоритма

Последовательная сложность алгоритма равна $O(C_1 m + C_2n)$, где

• $C_1$ – количество операций уменьшения расстояния до вершины;
• $C_2$ – количество операций вычисления минимума.

Оригинальный алгоритм Дейкстры использовал в качестве внутренней структуры данных списки, для которых $C_1 = O(1)$, $C_2 = O(n)$, так что общая сложность составляла $O(n^2)$.

При использовании фибоначчиевой кучи время вычисления минимума сокращается до $C_2 = O(\ln n)$, так что общая сложность равна $O(m + n \ln n)$, что является асимптотически наилучшим известным результатом для данного класса задач.

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

Алгоритм Дейкстры допускает эффективную параллелизацию, среднее время работы $O(n^{1/3}\ln n)$ с объёмом вычислений $O(n \ln n + m)$.

Алгоритм Δ-шагания может рассматриваться как параллельная версия алгоритма Дейкстры.

1.9 Описание входных и выходных данных

Входные данные: взвешенный граф $(V, E, W)$ ($n$ вершин $v_i$ и $m$ рёбер $e_j = (v^{(1)}_{j}, v^{(2)}_{j})$ с весами $f_j$), вершина-источник $u$.

Объём входных данных: $O(m + n)$.

Выходные данные (возможные варианты):

1. для каждой вершины $v$ исходного графа – последнее ребро $e^*_v = (w, v)$, лежащее на кратчайшем пути от вершины $u$ к $v$, или соответствующая вершина $w$;
2. для каждой вершины $v$ исходного графа – суммарный вес $f^*(v)$ кратчайшего пути от от вершины $u$ к $v$.

Объём выходных данных: $O(n)$.

2 Программная реализация алгоритмов

2.7 Существующие реализации алгоритма

• C++: Boost Graph Library (функции dijkstra_shortest_paths, dijkstra_shortest_paths_no_color_map), сложность $O(m + n \ln n)$.
• C++, MPI: Parallel Boost Graph Library:
  • функция eager_dijkstra_shortest_paths – непосредственная реализация алгоритма Дейкстры;
  • функция crauser_et_al_shortest_paths – реализация алгоритма Дейкстры в виде алгоритма из статьи Краузера и др.
• Python: NetworkX (функция single_source_dijkstra).
• Python/C++: NetworKit (класс networkit.graph.Dijkstra).