Dérouler Dijkstra

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

Énoncé

Dérouler l'algorithme de Dijkstra sur le réseau routier ${Paris \leftrightarrow Lille (225), Paris \leftrightarrow Nantes (385), Paris \leftrightarrow Lyon (465), Lyon \leftrightarrow Marseille (315)}$ depuis la source Paris.

Corrigé

Initialisation : $dist [Paris] = 0$ , autres $= \infty$ . Sommets non figés : ${Paris, Lille, Nantes, Lyon, Marseille}$ .
Tour 1 : Extraire le minimum (Paris, 0). Relâcher ses voisins :
$dist [Lille] = 225$
$dist [Nantes] = 385$
$dist [Lyon] = 465$ . Paris est figé.
Tour 2 : Extraire le minimum (Lille, 225). Aucun relâchement possible. Lille est figée.
Tour 3 : Extraire le minimum (Nantes, 385). Aucun relâchement possible. Nantes est figée.
Tour 4 : Extraire le minimum (Lyon, 465). Relâcher son voisin Marseille :
$dist [Marseille] = dist [Lyon] + 315 = 465 + 315 = 780$ . Lyon est figée.
Tour 5 : Extraire le minimum (Marseille, 780). Marseille est figée. Distances finales : Lille (225), Nantes (385), Lyon (465), Marseille (780).

Les autres exercices de ce chapitre Le cours du chapitre

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