Сложность алгоритма

Сложность алгоритма Дейкстры зависит от способа нахождения вершины v, а также способа хранения множества непосещенных вершин и способа обновления меток. Обозначим через n количество вершин, а через m — количество ребер в графе G.

• В простейшем случае, когда для поиска вершины с минимальным d [ v ] просматривается все множество вершин, а для хранения величин d — массив, время работы алгоритма есть O (n ² + m). Основной цикл выполняется порядка n раз, в каждом из них на нахождение минимума тратится порядка n операций, плюс количество релаксаций (смен меток), которое не превосходит количества ребер в исходном графе.

• Для разреженных графов (то есть таких, для которых m много меньше n²) непосещенные вершины можно хранить в двоичной куче, а в качестве ключа использовать значения d [ i ], тогда время извлечения вершины из станет log n, при том, что время модификации d [ i ] возрастет до log n. Так как цикл выполняется порядка n раз, а количество релаксаций не больше m, скорость работы такой реализации O (n log n + m log n)

• Если для хранения непосещенных вершин использовать фибоначчиеву кучу, для которой удаление происходит в среднем за O (log n), а уменьшение значения в среднем за O (1), то время работы алгоритма составит O (n log n + m). Однако, согласно сайту intuit.ru,

скрытые константы в асимптотических оценках трудоемкости велики и использование фибоначчиевых куч редко оказывается целесообразным: обычные двоичные (d-ичные) кучи на практике эффективнее.

Альтернативами им служат толстые кучи, тонкие кучи и кучи Бродала, обладающие теми же асимптотическими оценками, но меньшими константами.