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

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

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

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

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

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

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

[math]\displaystyle{ (v, w) \in \arg\min \{ d(v) + f(e) \mid v \in V, e = (v, w) \in E \}. }[/math]

Тогда [math]\displaystyle{ d(w) = d(v) + f(e) }[/math], и [math]\displaystyle{ v }[/math] лежит на кратчайшем пути от [math]\displaystyle{ u }[/math] к [math]\displaystyle{ w }[/math].

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

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

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

Последовательная сложность алгоритма равна [math]\displaystyle{ O(C_1 m + C_2n) }[/math], где

• [math]\displaystyle{ C_1 }[/math] – количество операций уменьшения расстояния до вершины;
• [math]\displaystyle{ C_2 }[/math] – количество операций вычисления минимума.

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

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

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

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

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

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

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

• C++: Boost Graph Library (функции dijkstra_shortest_paths, dijkstra_shortest_paths_no_color_map), сложность [math]\displaystyle{ O(m + n \ln n) }[/math].
• 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).