Dijkstra, déroulé

Le déroulé mesuré (la file est notée par couples (estimation, sommet)) :

etape 1 : on fige 0 (d=0)   d = [0; inf; inf; inf; inf; inf]  file = []
etape 2 : on fige 1 (d=7)   d = [0; 7; 9; inf; inf; 14]       file = [(9,2); (14,5)]
etape 3 : on fige 2 (d=9)   d = [0; 7; 9; 22; inf; 14]        file = [(14,5); (22,3)]
etape 4 : on fige 5 (d=11)  d = [0; 7; 9; 20; inf; 11]        file = [(14,5); (20,3); (22,3)]
etape 5 : on fige 3 (d=20)  d = [0; 7; 9; 20; 20; 11]         file = [(20,4); (22,3)]
etape 6 : on fige 4 (d=20)  d = [0; 7; 9; 20; 20; 11]         file = [(22,3)]

distances finales : [0; 7; 9; 20; 20; 11]
peres             : [-; 0; 0; 2; 5; 2]

Trois observations, et chacune éclaire un point du chapitre.

• L'étape 4 fige $5$ avec $d=11$, alors que la file contenait encore $(14,5)$. La valeur $14$ était l'estimation par l'arête directe $0-5$ ; l'estimation $11$ est venue plus tard, par $0\to 2\to 5$ ($9+2$). Les deux coexistent dans la file : c'est le doublon du chapitre. L'extraction rend la plus petite, et la seconde sera ignorée.
• Le sommet $3$ change deux fois d'estimation : $22$ par $1\to 3$ ($7+15$), puis $20$ par $2\to 3$ ($9+11$). Deux entrées dans la file, dont une seule utile.
• Les sommets $3$ et $4$ sont tous deux à distance $20$. L'un est atteint par $0\to 2\to 3$, l'autre par $0\to 2\to 5\to 4$. L'ordre entre eux dépend de la file de priorité, pas de l'algorithme : Dijkstra ne définit pas un ordre total sur les sommets de même distance, et un test qui exigerait un ordre précis serait fragile.

Les chemins, reconstruits depuis le tableau des pères : $0\to 1$ (7), $0\to 2$ (9), $0\to 2\to 3$ (20), $0\to 2\to 5\to 4$ (20), $0\to 2\to 5$ (11). Noter que le plus court chemin vers $4$ ne passe pas par $3$, alors que $3$ et $4$ sont à la même distance : la table des pères est la seule source de vérité sur les chemins.