Algorithme de Dijkstra - Étape par étape
L'algorithme de Dijkstra (prononcer approximativement « Dextra ») permet de trouver le plus court chemin entre deux sommets d'un graphe (orienté ou non orienté). Dans l'exemple du graphe ci-dessous, on va rechercher le chemin le plus court menant de M à S.
Initialisation :
On construit un tableau ayant pour colonnes chacun des sommets du graphe. On ajoute à gauche une colonne qui recensera les sommets choisis à chaque étape (cette colonne est facultative mais facilitera la compréhension de l'algorithme).
Puisque l'on part du sommet M, on inscrit, sur la première ligne intitulée « Départ », dans la colonne M et \bm{\infty} dans les autres colonnes.
Cela signifie qu'à ce stade, on peut rejoindre M en 0 minute et on n'a rejoint aucun autre sommet puisque l'on n'a pas encore emprunté de chemin...
Étape 1 :
On sélectionne le plus petit résultat de la dernière ligne. Ici, c'est « » qui correspond au chemin menant au sommet M en 0 minute.
On met en évidence cette sélection (nous l'écrirons en rouge mais il est également possible de la souligner, de l'entourer, etc.).
On inscrit le sommet retenu et la durée correspondante dans la première colonne (ici on écrit M(0)).
On désactive les cases situées en dessous de notre sélection en les grisant par exemple. En effet, on a trouvé le trajet le plus court menant à M ; il sera inutile d'en chercher d'autres.
À partir de M, on voit sur le graphe que l'on peut rejoindre E, L et N en respectivement 10, 7 et 4 minutes. Ces durées sont les durées les plus courtes ; elles sont inférieures au durées inscrites sur la ligne précédente qui étaient « ».
On inscrit donc \bm{10_{\text{M}}, 7_{\text{M}}} et \bm{4_{\text{M}}} dans les colonnes E, L et N. Le M situé en indice signifie que l'on vient du sommet M.
Enfin on complète la ligne en recopiant dans les cellules vides les valeurs de la ligne précédente.
Étape 2 :
On sélectionne le plus petit résultat de la dernière ligne. Ici, c'est « » qui correspond au chemin menant au sommet N en 4 minutes.
On met en évidence cette sélection.
On inscrit le sommet retenu et la durée correspondante dans la première colonne : N (4).
On désactive les cases situées en dessous de notre sélection. On a trouvé le trajet le plus court menant à N ; il dure 4 minutes.
À partir de N, on peut rejoindre L et S (on ne se préoccupe plus de M qui a été « désactivé »).
Si l'on rejoint L : On mettra 2 minutes pour aller de N à L et 4 minutes pour aller de M à N (ces 4 minutes sont inscrites dans la première colonne) soit au total 6 minutes. Ce trajet est plus rapide que le précédent qui durait 7 minutes. On indique donc \bm{6_{\text{N}}} dans la colonne L. Le N situé en indice signifie que l'on vient du sommet N.
Si l'on rejoint S : On mettra 8 minutes pour aller de N à S et 4 minutes pour aller de M à N soit au total 12 minutes. Ce trajet est plus rapide que le précédent qui était . On indique donc \bm{12_{\text{N}}} dans la colonne S.
Puis on complète la ligne en recopiant dans les cellules vides les valeurs de la ligne précédente.
Étape 3 :
On sélectionne le plus petit résultat de la dernière ligne. Ici, c'est « » qui correspond au chemin menant au sommet L en 6 minutes.
On met en évidence cette sélection.
On inscrit le sommet retenu et la durée correspondante dans la première colonne : L (6).
On désactive les cases situées en dessous de notre sélection. On a trouvé le trajet le plus court menant à L ; il dure 6 minutes.
À partir de L, on peut rejoindre E et S (on ne se préoccupe plus de M ni de N qui ont été « désactivés »).
Si l'on rejoint E : On mettra 8 minutes pour aller de L à E et 6 minutes pour aller de M à L soit, au total, 14 minutes. Ce trajet N'EST PAS plus rapide que le précédent qui durait 10 minutes.
On se contente donc de recopier le contenu précédent \bm{10_{\text{M}}} dans la colonne E.
Si l'on rejoint S : On mettra 5 minutes pour aller de L à S et 6 minutes pour aller de M à L soit au total 11 minutes. Ce trajet est plus rapide que le précédent qui durait 12 minutes. On indique donc \bm{11_{\text{L}}} dans la colonne S.
Important !
On inscrit la durée d'un trajet dans le tableau uniquement si elle est inférieure à la durée figurant sur la ligne précédente. Dans le cas contraire, on recopie la valeur précédente.
Puis on complète la ligne en recopiant dans les cellules vides les valeurs de la ligne précédente.
Étape 4 :
On sélectionne le plus petit résultat. C'est « » qui correspond au chemin menant au sommet E en 10 minutes.
On met en évidence cette sélection.
On inscrit le sommet retenu et la durée correspondante dans la première colonne : E (10).
On désactive les cases situées en dessous de notre sélection. On a trouvé le trajet le plus court menant à E ; il dure 10 minutes.
À partir de E, on peut rejoindre S et T (on ne se préoccupe plus des autres sommets qui ont été « désactivés »).
Si l'on rejoint S : On mettra 10 minutes pour aller de E à S et 10 minutes pour aller de M à E (ces 10 minutes sont inscrites dans la première colonne) soit au total 20 minutes.
Ce trajet N'EST PAS plus rapide que le précédent qui durait 11 minutes. On se contente donc de recopier le contenu précédent \bm{11_{\text{L}}} dans la colonne S.
Si l'on rejoint T : On mettra 4 minutes pour aller de E à T et 10 minutes pour aller de M à E soit au total 14 minutes. Ce trajet est plus rapide que le précédent qui était . On indique donc \bm{14_{\text{E}}} dans la colonne T.
Étape 5 :
On sélectionne le plus petit résultat. C'est « » qui correspond au chemin menant au sommet S en 11 minutes.
On a trouvé le trajet le plus court menant à S : il dure 11 minutes. Comme c'est la question posée dans l'énoncé, il est inutile d'aller plus loin et le tableau est terminé !
Il reste toutefois à reconstituer le trajet qui correspond à cette durée de 11 minutes. En pratique, il est plus facile de trouver le trajet en sens inverse en « remontant » dans le tableau de la façon suivante :
On part de notre point d'arrivée : S
On recherche la cellule marquée en rouge de la colonne S ; elle contient . On note la lettre écrite en indice : L.
On recherche la cellule marquée en rouge de la colonne L ; elle contient . On note la lettre écrite en indice : N.
On recherche la cellule marquée en rouge de la colonne N ; elle contient . On note la lettre écrite en indice : M.
On est arrivé à notre point de départ M après être passé par N et L et S (liste obtenue en listant les sommets en ordre inverse).
Le trajet optimal est donc M - N - L - S.
Enfin, on peut vérifier sur le graphe que ce trajet est correct et dure 11 minutes !