Algorithme de Dijkstra

DijkstraEdsgerWDijkstra, Edsger W.: élaboré en 1956, publié en 1959, 10/02/2024 11:11:55

Besoin

Algorithme de PCC pour les coûts d'arêtes >= 0 (ou variables).

Analyse

À partir d'un sommet de départ, examiner l'ensemble des nœuds les plus proches, plus l'ensemble des nœuds un niveau plus loin, etc.

Conception

Parcours du graphe depuis une source, en largeur d'abord.

Tout au long du calcul, on maintient 2 ensembles :

Exemples

Notes

s1Athanasios, Papagelis: "Dijkstra algorithm", You just found... my message in Cyberspace Ocean