informatique (tronc commun des prépas scientifiques) · Chapitre 14 · Exercice de TD
Étapes ou kilomètres ? Les deux réponses sur un même graphe
Plus courts chemins : Dijkstra et au-delà · niveau 2
É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.