Étapes ou kilomètres ? Les deux réponses sur un même graphe
Exercice · informatique (tronc commun des prépas scientifiques), chapitre 14 — Plus courts chemins : Dijkstra et au-delà
Énoncé
Démontrer que sur un graphe dont les arcs ont tous un poids égal à 1, Dijkstra produit les mêmes résultats que le BFS.
Corrigé
Si tous les poids valent 1, le poids total d'un chemin correspond exactement à son nombre d'arcs. Lors de l'exécution de Dijkstra, les distances provisoires des sommets à traiter sont des entiers successifs. L'extraction systématique du minimum de distance provisoire revient à traiter les sommets dans l'ordre strict de leur nombre d'arcs à la source. L'ordre de figeage coïncide donc exactement avec l'ordre d'exploration FIFO d'une file de BFS.
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.