Алгоритм Дейкстры: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Daryin (обсуждение | вклад) |
Daryin (обсуждение | вклад) |
||
| Строка 21: | Строка 21: | ||
=== Информационный граф === | === Информационный граф === | ||
=== Описание ресурса параллелизма алгоритма === | === Описание ресурса параллелизма алгоритма === | ||
Алгоритм Дейкстры допускает эффективную параллелизацию<ref>Crauser, A, K Mehlhorn, U Meyer, and P Sanders. “A Parallelization of Dijkstra's Shortest Path Algorithm,” Proceedings of Mathematical Foundations of Computer Science / Lecture Notes in Computer Science, 1450:722–31, Berlin, Heidelberg: Springer, 1998. doi:10.1007/BFb0055823.</ref>, среднее время работы <math>O(n^{1/3}\ln n)</math> с объёмом вычислений <math>O(n \ln n + m)</math>. | |||
[[Алгоритм Δ-шагания]] может рассматриваться как параллельная версия алгоритма Дейкстры. | |||
=== Описание входных и выходных данных === | === Описание входных и выходных данных === | ||
=== Свойства алгоритма=== | === Свойства алгоритма=== | ||
Версия от 16:17, 11 июня 2015
Свойства и структура алгоритмов
Общее описание алгоритма
Алгоритм Дейкстры[1] предназначен для решения задачи поиска кратчайшего пути на графе. Для заданного ориентированного взвешенного графа с неотрицательными весами алгоритм находит кратчайшие расстояния от выделенной вершины-источника до всех остальных вершин графа. Алгоритм Дейкстры (с использованием фибоначчиевой кучи[2]) выполняется за время [math]\displaystyle{ O(m + n \ln n) }[/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].
При использовании фибоначчиевой кучи[2] время вычисления минимума сокращается до [math]\displaystyle{ C_2 = O(\ln n) }[/math], так что общая сложность равна [math]\displaystyle{ O(m + n \ln n) }[/math], что является асимптотически наилучшим известным результатом для данного класса задач.
Информационный граф
Описание ресурса параллелизма алгоритма
Алгоритм Дейкстры допускает эффективную параллелизацию[3], среднее время работы [math]\displaystyle{ O(n^{1/3}\ln n) }[/math] с объёмом вычислений [math]\displaystyle{ O(n \ln n + m) }[/math].
Алгоритм Δ-шагания может рассматриваться как параллельная версия алгоритма Дейкстры.
Описание входных и выходных данных
Свойства алгоритма
Программная реализация алгоритмов
Особенности реализации последовательного алгоритма
Описание локальности данных и вычислений
Возможные способы и особенности реализации параллельного алгоритма
Масштабируемость алгоритма и его реализации
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
- Boost Graph Library (функции
dijkstra_shortest_paths,dijkstra_shortest_paths_no_color_map), сложность [math]\displaystyle{ O(m + n \ln n) }[/math].
Литература
- ↑ 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,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.
- ↑ Crauser, A, K Mehlhorn, U Meyer, and P Sanders. “A Parallelization of Dijkstra's Shortest Path Algorithm,” Proceedings of Mathematical Foundations of Computer Science / Lecture Notes in Computer Science, 1450:722–31, Berlin, Heidelberg: Springer, 1998. doi:10.1007/BFb0055823.