L'algorithme dû à Dijkstra est basé sur le principe suivant :

Si le plus court chemin reliant le sommet de départ s0s0 à un autre sommet S passe par les sommets s1s1, s2s2, …, sksk alors, les différentes étapes sont aussi les plus courts chemins reliant A aux différents sommets s1s1, s2s2, …, sksk.

On construit de proche en proche le chemin cherché en choisissant à chaque itération de l'algorithme, un sommet sisi du graphe parmi ceux qui n'ont pas encore été traités, tel que la longueur connue provisoirement du plus court chemin allant de s0s0 à sisi soit la plus courte possible.

https://fe.fil.univ-lille1.fr/sntcarto/media/Phil_Clem_localisation-cartographie-03.pdf