OCaml (option informatique) · Chapitre 16 · Application directe du cours
Le pas de relâchement
Plus courts chemins : Dijkstra · niveau 1 (application)
Énoncé
Expliquer ce que calcule if dist.(u) + poids < dist.(v) then dist.(v) <- dist.(u) + poids et pourquoi c'est le cœur de Dijkstra.
Corrigé
Le relâchement teste si atteindre v en passant par u (distance dist.(u) jusqu'à u, plus le poids de l'arête) est meilleur que la meilleure distance connue à v ; si oui, on met à jour. Dijkstra n'est qu'une discipline de relâchements : relâcher les arêtes des sommets dans l'ordre de leur distance croissante garantit qu'on ne relâche jamais à partir d'une distance non définitive.
Exercices semblables
- Reconstruire le chemin corrigé
- Floyd-Warshall (toutes les paires) corrigé
- Bellman-Ford (poids négatifs) corrigé
- Graphe pondéré corrigé
- Longueur d'un chemin corrigé