Le pas de relâchement
Exercice · OCaml (option informatique), chapitre 16 — Plus courts chemins : Dijkstra
É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.
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.