Le détour gagnant

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 14 — Plus courts chemins : Dijkstra et au-delà

Énoncé

Sur le graphe ${s 7 a, s 2 b, a 3 b}$ , expliquer comment Dijkstra s'aperçoit que le chemin direct $s 7 a$ est sous-optimal.

Initialement, $dist [a] = 7$ (via l'arc $s \to a$ ) et $dist [b] = 2$ (via $s \to b$ ).
Au tour suivant, l'algorithme extrait le minimum parmi ${a, b}$ , soit $b$ (distance 2).
Lors du relâchement des arcs sortants de $b$ , l'algorithme examine l'arc $b \to a$ de poids 3 : $dist [b] + w (b, a) = 2 + 3 = 5 < dist [a] = 7$
La distance provisoire de $a$ est mise à jour à 5, et son père devient $b$ . Le détour par $b$ est validé.

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.