OCaml (option informatique) · Chapitre 16 · Exercice de TD
Poids unitaires
Plus courts chemins : Dijkstra · niveau 2
É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.
Exercices semblables
- Dijkstra corrigé
- Distance entre deux sommets corrigé
- Le contre-exemple des poids négatifs corrigé
- Reconstruire le chemin corrigé
- Floyd-Warshall (toutes les paires) corrigé