Poids unitaires
Exercice · OCaml (option informatique), chapitre 16 — Plus courts chemins : Dijkstra
Énoncé
Montrer que, si tous les poids valent 1, Dijkstra donne les mêmes distances qu'un BFS.
Corrigé
Avec des poids tous égaux à 1, la distance pondérée d'un chemin est son nombre d'arêtes. Choisir le sommet non traité de distance minimale revient alors à traiter les sommets par nombre d'arêtes croissant — exactement l'ordre du BFS. Dijkstra généralise donc le BFS aux poids quelconques (positifs) : pour des poids unitaires, le BFS (en ) est préférable car plus simple et plus rapide.
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.