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

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

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

Алгоритм Дейкстры предназначен для решения задачи поиска кратчайшего пути на графе. Для заданного ориентированного взвешенного графа с неотрицательными весами алгоритм находит кратчайшие расстояния от выделенной вершины-источника до всех остальных вершин графа. Алгоритм Дейкстры (с использованием фибоначчиевой кучи) выполняется за время [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].

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