Tableau de Moore-Dijkstra Pondichéry TES spé 2014
EXERCICE :
Voici un graphe non orienté
Donner le chemin de A à H de durée minimale.
( Les coefficients sont en minutes )
--------------------------------------------------------------------------------------------------------------
REPONSE:
Tableau de Moore-Dijkstra.
Bilan:
La durée minimale est 23 minutes.
Un trajet minimal possible:
H ← F( 23) ← G( 16) ← D( 12 ) ← B( 10 ) ← A( 3 ) ← A ( 0 )
ou encore :
H ← F( 23) ← G( 16) ← D( 12 ) ← C( 10 ) ← B( 6 ) ← A ( 3 ) ←A(0)
Conclusion : Le trajet le plus court en durée est ABDGFH de 23 minutes
ou encore ABCDGFH de durée 23 minutes aussi
---------------------------------------------------------------------------------------------------