 |
Plus court chemin de E à S ?
Algorithme de Dijkstra (Principe) : On avance par le noeud de plus petit poids (car il est déjà optimum) |
 |
Pondérations initiales des noeuds :
0 pour le noeud de départ E , ∞ pour les autres noeuds. |
 |
plus petit poids : 0 pour le noeud E
prise en compte des trajets partant de E poids(A)=30 poids(B)=10 |
 |
plus petit poids : 10 pour le noeud B
prise en compte des trajets partant de B poids(A)=20 (diminué) donc : l'arête EA ne fait pas partie du trajet le plus court poids(D)=40 poids(C)=60 |
 |
plus petit poids : 20 pour le noeud A
prise en compte des trajets partant de A poids(D)=40 |
 |
plus petit poids : 40 pour le noeud D
prise en compte des trajets partant de D poids(S)=70 poids(C)=50 (diminué) donc : l'arête BC ne fait pas partie du trajet le plus court |
 |
plus petit poids : 50 pour le noeud C
prise en compte des trajets partant de C poids(S)=60 (diminué) donc : l'arête DS ne fait pas partie du trajet le plus court poids(plus court trajet de E à S) = 60 les 2 trajets possibles sont : EBADCS et EBDCS |