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 $0$ 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 $X$ de coefficient minimal.
- Commencer une nouvelle ligne et rayer toutes les cases vides sous $X$.
- Étape 3 : pour chaque sommet $Y$ adjacent à $X$, calculer la somme $P$ du coefficient de $X$ et du poids de l’arête reliant $Y$ à $X$.
- Si $P$ est strictement inférieur au coefficient de $Y$, inscrire $PX$ dans la case correspondante de la colonne $Y$.
- Sinon, inscrire le coefficient de $Y$ 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 :
On cherche à déterminer la plus courte chaîne menant de $S$ à $E$.
Placer tous les sommets du graphe dans la première ligne d’un tableau et d’écrire le coefficient $0$ sous le sommet de départ et le coefficient $\infty$ sous les autres sommets.
| $S$ | $A$ | $I$ | $U$ | $V$ | $B$ | $E$ |
| $0$ | $\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.
| $S$ | $A$ | $I$ | $U$ | $V$ | $B$ | $E$ |
| $0$ | $\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 $S$-$A$ est $9$ alors que le poids de la chaîne $S$-$I$ est $12$.
| $S$ | $A$ | $I$ | $U$ | $V$ | $B$ | $E$ |
| $0$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ |
| / | $9,S$ | $12,S$ | $20,S$ | $\infty$ | $\infty$ | $\infty$ |
| / | ||||||
| / | ||||||
| / | ||||||
| / | ||||||
| / |
Il reste des sommets non traités : $V$, $B$ et $E$.
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 $U$, on a le choix entre $S$-$U$ de poids $20$ ou $S$-$A$-$U$ de poids $17$.
On inscrit le poids minimal dans le tableau en on complète avec le coefficient $\infty$ sous les sommets non adjacents.
| $S$ | $A$ | $I$ | $U$ | $V$ | $B$ | $E$ |
| $0$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ |
| / | $9,S$ | $12,S$ | $20,S$ | $\infty$ | $\infty$ | $\infty$ |
| / | / | $12,S$ | $17,A$ | $30,A$ | $\infty$ | $\infty$ |
| / | / | |||||
| / | / | |||||
| / | / | |||||
| / | / |
À nouveau l’étape 2 :
| $S$ | $A$ | $I$ | $U$ | $V$ | $B$ | $E$ |
| $0$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ |
| / | $9,S$ | $12,S$ | $20,S$ | $\infty$ | $\infty$ | $\infty$ |
| / | / | $12,S$ | $17,A$ | $30,A$ | $\infty$ | $\infty$ |
| / | / | / | ||||
| / | / | / | ||||
| / | / | / | ||||
| / | / | / |
Puis l’étape 3 :
| $S$ | $A$ | $I$ | $U$ | $V$ | $B$ | $E$ |
| $0$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ |
| / | $9,S$ | $12,S$ | $20,S$ | $\infty$ | $\infty$ | $\infty$ |
| / | / | $12,S$ | $17,A$ | $30,A$ | $\infty$ | $\infty$ |
| / | / | / | $16,I$ | $30,A$ | $25,I$ | $\infty$ |
| / | / | / | ||||
| / | / | / | ||||
| / | / | / |
On recommence l’opération jusqu’à ce que tous les sommets soient sélectionnés.
| $S$ | $A$ | $I$ | $U$ | $V$ | $B$ | $E$ |
| $0$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ |
| / | $9,S$ | $12,S$ | $20,S$ | $\infty$ | $\infty$ | $\infty$ |
| / | / | $12,S$ | $17,A$ | $30,A$ | $\infty$ | $\infty$ |
| / | / | / | $16,I$ | $30,A$ | $25,I$ | $\infty$ |
| / | / | / | / | $27,U$ | $23,U$ | $\infty$ |
| / | / | / | / | $27,U$ | / | $32,B$ |
| / | / | / | / | / | / | $30,V$ |
Le poids minimal se lit sur la dernière ligne du tableau, c’est-à-dire $30$.
La plus courte chaîne menant de $S$ à $E$ se lit également dans le tableau : il s’agit de la chaîne $S$-$I$-$U$-$V$-$E$ de poids $30$.