Алгоритм Дейкстры: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Daryin (обсуждение | вклад) |
Daryin (обсуждение | вклад) |
||
| Строка 10: | Строка 10: | ||
=== Описание схемы реализации последовательного алгоритма === | === Описание схемы реализации последовательного алгоритма === | ||
=== Последовательная сложность алгоритма === | === Последовательная сложность алгоритма === | ||
Последовательная сложность алгоритма равна <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>. | |||
При использовании фибоначчиевой кучи<ref name=FibHeap /> время вычисления минимума сокращается до <math>C_2 = O(\ln n)</math>, так что общая сложность равна <math>O(m + n \ln n)</math>, что является асимптотически наилучшим известным результатом для данного класса задач. | |||
=== Информационный граф === | === Информационный граф === | ||
=== Описание ресурса параллелизма алгоритма === | === Описание ресурса параллелизма алгоритма === | ||
Версия от 21:57, 10 июня 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], что является асимптотически наилучшим известным результатом для данного класса задач.
Информационный граф
Описание ресурса параллелизма алгоритма
Описание входных и выходных данных
Свойства алгоритма
Программная реализация алгоритмов
Особенности реализации последовательного алгоритма
Описание локальности данных и вычислений
Возможные способы и особенности реализации параллельного алгоритма
Масштабируемость алгоритма и его реализации
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
Литература
- ↑ 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.