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

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

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

Алгоритм Дейкстры предназначен для решения задачи поиска кратчайшего пути на графе. Для заданного ориентированного взвешенного графа с неотрицательными весами алгоритм находит кратчайшие расстояния от выделенной вершины-источника до всех остальных вершин графа. Алгоритм Дейкстры (с использованием фибоначчиевой кучи) выполняется за время [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].

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

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

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

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

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

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

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

Q := new priority queue
for each v ∈ V:
    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))

Описание схемы реализации последовательного алгоритма

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

Возможен вариант реализации, когда вершины добавляются в очередь не на этапе инициализации, а в момент первого посещения.

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

Последовательная сложность алгоритма равна [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].

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

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

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

Объём входных данных: [math]\displaystyle{ O(m + n) }[/math].

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

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

Объём выходных данных: [math]\displaystyle{ O(n) }[/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).