Savoir utiliser l'algorithme de Dijkstra-Moore - Mathématiques

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$ .

Pré-requis

Etapes