Maths-cours

COURS & EXERCICES DE MATHÉMATIQUES

Close

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 », 0M0_{\text{M}} 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 « 0M0_{\text{M}} » qui correspond au chemin menant au sommet M en 0 minute.

À 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 « \infty ».

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 « 4M4_{\text{M}} » qui correspond au chemin menant au sommet N en 4 minutes.

À partir de N, on peut rejoindre L et S (on ne se préoccupe plus de M qui a été « désactivé »).

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 « 6N6_{\text{N}} » qui correspond au chemin menant au sommet L en 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 »).

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 « 10M10_{\text{M}} » qui correspond au chemin menant au sommet E en 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 »).

Étape 5 :

On sélectionne le plus petit résultat. C'est « 11L11_{\text{L}} » 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 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 !