Algorithme de Dijkstra

DijkstraEdsgerWEdsger W. Dijkstra: élaboré en 1956, publié en 1959

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