Dérouler Dijkstra

Dérouler Dijkstra

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

É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).

Énoncé

Corrigé

Exercices semblables