Adloun

informatique (tronc commun des prépas scientifiques) · Chapitre 14 · Application directe du cours

Le détour gagnant

Plus courts chemins : Dijkstra et au-delà · niveau 1 (application)

Énoncé

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

Corrigé

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

Exercices semblables

A* contre Dijkstra, le match mesuré corrigé
L'heuristique qui ment corrigé
Une source vers tous, tous vers un, un vers un corrigé
Dérouler Dijkstra corrigé
Reconstruire tous les chemins corrigé

Le cours du chapitre · Tous les exercices du chapitre