Алгоритм Дейкстры: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Daryin (обсуждение | вклад) |
Daryin (обсуждение | вклад) |
||
| Строка 41: | Строка 41: | ||
** функция <code>[http://www.boost.org/libs/graph_parallel/doc/html/dijkstra_shortest_paths.html#eager-dijkstra-s-algorithm eager_dijkstra_shortest_paths]</code> – непосредственная реализация алгоритма Дейкстры; | ** функция <code>[http://www.boost.org/libs/graph_parallel/doc/html/dijkstra_shortest_paths.html#eager-dijkstra-s-algorithm eager_dijkstra_shortest_paths]</code> – непосредственная реализация алгоритма Дейкстры; | ||
** функция <code>[http://www.boost.org/libs/graph_parallel/doc/html/dijkstra_shortest_paths.html#crauser-et-al-s-algorithm crauser_et_al_shortest_paths]</code> – реализация алгоритма Дейкстры в виде алгоритма из статьи Краузера и др.<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> | ** функция <code>[http://www.boost.org/libs/graph_parallel/doc/html/dijkstra_shortest_paths.html#crauser-et-al-s-algorithm crauser_et_al_shortest_paths]</code> – реализация алгоритма Дейкстры в виде алгоритма из статьи Краузера и др.<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> | ||
* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.shortest_paths.weighted.single_source_dijkstra.html single_source_dijkstra]</code>). | |||
== Литература == | == Литература == | ||
<references /> | <references /> | ||
Версия от 18:52, 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].
Алгоритм Δ-шагания может рассматриваться как параллельная версия алгоритма Дейкстры.
Описание входных и выходных данных
Свойства алгоритма
Программная реализация алгоритмов
Особенности реализации последовательного алгоритма
Описание локальности данных и вычислений
Возможные способы и особенности реализации параллельного алгоритма
Масштабируемость алгоритма и его реализации
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
- 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– реализация алгоритма Дейкстры в виде алгоритма из статьи Краузера и др.[4]
- функция
- Python: NetworkX (функция
single_source_dijkstra).
Литература
- ↑ 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.
- ↑ 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.