Puisque le comportement asymptotique de l'implémentation naïve de l'algorithme de Dijkstra est :
\(O(n^2 + m)\), alors à mesure que le nombre de sommets augmente, la vitesse de travail devient insatisfaisante.
Diverses structures de données peuvent être utilisées pour l'amélioration : tas de Fibonacci, ensembles
set ou une file d'attente prioritaire
priority_queue.
Prenons un exemple avec
set, par conséquent, l'asymptotique finale est :
\(O(n log (m))\) ,
détails.