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

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

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

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

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

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

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

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

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

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

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

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

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

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

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