EX DE BAC ES SPE France 2009
EXERCICE
Le graphe ci-dessous représente le plan d'une ville.
Le sommet A désigne l'emplacement des services techniques.
Les sommets B , C , D, E , F et G désignent les emplacements des jardins publics.
Une arête représente l'avenue reliant deux emplacements et est pondérée
par le nombre de feux tricolores situés sur le trajet.
Proposer un trajet, comportant un minimum de feux tricolores, reliant A à G
------------------------------------------------------------------------------------------
REPONSE
Faisons le tableau de Moore-Dijkstra pour le graphe pondéré donné
Conclusion : Un trajet, comportant un minimum de feux tricolores, reliant A à G est
ACEFG comportant 7 feux tricoores.
---------------------------------------------------------------------------