Так как асимптотика наивной реализации алгоритма Дейкстра:
\(O(n^2 + m)\), то с увеличением количества вершин скорость работы становиться неудовлетворительной.
Для улучшения можно использовать различные структуры данных: Фибоначчиевы кучи, множества
set или очередь с приоритетом
priority_queue.
Рассмотрим пример с
set, в результате итоговая асимптотика получается:
\(O(n log (m))\),
подробнее.
