Cliquer à l'intérieur du graphe pour trouver le plus court chemin entre A et I

Le plus court chemin =

Algorithme de Dijkstra (graphe orienté ou non,poids positif ou nul): Plus court chemin
1. Marquer le sommet-initial = 0 et les autres = ∞ , puis selectioner le sommet initial
2. Parmi les sommets non-traité (jaune), selectioner le minimum X (rouge) puis marquer le comme traité (bleu)
3. Minimiser les voisins Y(jaune) non-traité de X , c'est-à-dire
si X+(X,Y) < Y alors on prend Y=X+(X,Y)
4. Revenir en (2)
5. On s'arrête quand le sommet-fin est traité (bleu).


Accueil