Médaille
N°1 pour apprendre & réviser du collège au lycée.
Marianne

Conforme au programme
officiel 2018 - 2019

Savoir utiliser l'algorithme de Dijkstra-Moore
Savoir-faire

Pré-requis

L’algorithme de Dijkstra-Moore permet de trouver la plus courte chaîne reliant un sommet à un autre dans un graphe :

Étapes de l’Algorithme de Dijkstra-Moore

  • Étape 1 : placer tous les sommets du graphe dans la 1re ligne d’un tableau
  • Sur la 2e ligne du tableau, écrire le coefficient 00 sous le sommet de départ et le coefficient \infty sous les autres sommets.
  • Étape 2 : sur la dernière ligne écrite, repérer le sommet XX de coefficient minimal.
  • Commencer une nouvelle ligne et rayer toutes les cases vides sous XX.
  • Étape 3 : pour chaque sommet YY adjacent à XX, calculer la somme PP du coefficient de XX et du poids de l’arête reliant YY à XX.
  • Si PP est strictement inférieur au coefficient de YY, inscrire PXPX dans la case correspondante de la colonne YY.
  • Sinon, inscrire le coefficient de YY et compléter la ligne par des coefficients de la ligne précédente.
  • Étape 4 : s’il reste des sommets non sélectionnés, recommencer à l’étape 2.
  • Sinon, passer à l’étape 5.
  • Étape 5 : la longueur minimale est le nombre lu sur la dernière ligne du tableau.

À l’aide d’un exemple nous allons montrer comment utiliser l’algorithme de Dijkstra-Moore.

On considère le graphe ci-dessous :

graphe spécialité mathématiques terminale ES

On cherche à déterminer la plus courte chaîne menant de SS à EE.

Etapes

Placer tous les sommets du graphe dans la première ligne d’un tableau et d’écrire le coefficient 00 sous le sommet de départ et le coefficient \infty sous les autres sommets.

SS AA II UU VV BB EE
00 \infty \infty \infty \infty \infty \infty
             
             
             
             
             
             

Repérer sur la ligne écrite le sommet de coefficient minimal et de rayer toutes les cases vides sous ce sommet.

SS AA II UU VV BB EE
00 \infty \infty \infty \infty \infty \infty
/
/
/
/
/
/

Pour tous les sommets adjacents à ce sommet de coefficient minimal, on calcule le poids de la chaîne et sous tous les sommets non adjacents, on écrit le coefficient \infty.

Ici, le poids de la chaîne SS-AA est 99 alors que le poids de la chaîne SS-II est 1212.

SS AA II UU VV BB EE
00 \infty \infty \infty \infty \infty \infty
/ 9,S9,S 12,S12,S 20,S20,S \infty \infty \infty
/
/
/
/
/

Il reste des sommets non traités : VV, BB et EE.

On recommence alors la deuxième étape, on cherche le sommet de coefficient minimal, on le repère et on raye toutes les cases vides sous ce sommet.

On recommence la troisième étape.

En regardant bien le graphe, tu peux remarquer que, pour atteindre le sommet UU, on a le choix entre SS-UU de poids 2020 ou SS-AA-UU de poids 1717.

On inscrit le poids minimal dans le tableau en on complète avec le coefficient \infty sous les sommets non adjacents.

SS AA II UU VV BB EE
00 \infty \infty \infty \infty \infty \infty
/ 9,S9,S 12,S12,S 20,S20,S \infty \infty \infty
/ / 12,S12,S 17,A17,A 30,A30,A \infty \infty
/ /
/ /
/ /
/ /

À nouveau l’étape 2 :

SS AA II UU VV BB EE
00 \infty \infty \infty \infty \infty \infty
/ 9,S9,S 12,S12,S 20,S20,S \infty \infty \infty
/ / 12,S12,S 17,A17,A 30,A30,A \infty \infty
/ / /
/ / /
/ / /
/ / /

Puis l’étape 3 :

SS AA II UU VV BB EE
00 \infty \infty \infty \infty \infty \infty
/ 9,S9,S 12,S12,S 20,S20,S \infty \infty \infty
/ / 12,S12,S 17,A17,A 30,A30,A \infty \infty
/ / / 16,I16,I 30,A30,A 25,I25,I \infty
/ / /
/ / /
/ / /

On recommence l’opération jusqu’à ce que tous les sommets soient sélectionnés.

SS AA II UU VV BB EE
00 \infty \infty \infty \infty \infty \infty
/ 9,S9,S 12,S12,S 20,S20,S \infty \infty \infty
/ / 12,S12,S 17,A17,A 30,A30,A \infty \infty
/ / / 16,I16,I 30,A30,A 25,I25,I \infty
/ / / / 27,U27,U 23,U23,U \infty
/ / / / 27,U27,U / 32,B32,B
/ / / / / / 30,V30,V

Le poids minimal se lit sur la dernière ligne du tableau, c’est-à-dire 3030.
La plus courte chaîne menant de SS à EE se lit également dans le tableau : il s’agit de la chaîne SS-II-UU-VV-EE de poids 3030.