Алгоритм Дейкстры: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Строка 31: Строка 31:
 
=== Выводы для классов архитектур ===
 
=== Выводы для классов архитектур ===
 
=== Существующие реализации алгоритма ===
 
=== Существующие реализации алгоритма ===
 +
 +
* [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функции <code>[http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html dijkstra_shortest_paths]</code>, <code>[http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths_no_color_map.html dijkstra_shortest_paths_no_color_map]</code>), сложность <math>O(m + n \ln n)</math>.
 +
 
== Литература ==
 
== Литература ==
  
 
<references />
 
<references />

Версия 00:58, 11 июня 2015

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

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

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

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

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

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

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

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].

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

1.7 Информационный граф

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

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

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

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

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

2.2 Описание локальности данных и вычислений

2.3 Возможные способы и особенности реализации параллельного алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

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

3 Литература

  1. Dijkstra, E W. “A Note on Two Problems in Connexion with Graphs.” Numerische Mathematik 1, no. 1 (December 1959): 269–71. doi:10.1007/BF01386390.
  2. 2,0 2,1 Fredman, Michael L, and Robert Endre Tarjan. “Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms.” Journal of the ACM 34, no. 3 (July 1987): 596–615. doi:10.1145/28869.28874.