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