EXERCICE SUR LES GRAPHES TES spé maths.
EXERCICE 4
Trouver le trajet de durée minimale
de A à F du graphe G suivant.
( La pondération est en minutes )
-------------------------------------------------------------------------------------------------------------------
REPONSE:
• Méthode sur le graphe:
F ← 16(C) ← 11(A) ← A
Donc:
Conclusion : le chemin le plus court est : ACF de 16 mn
• Avec le tableau de Moore:
Il vient:
F ← C ( 16 ) ← A( 11) ← A
Conclusion : Le chemin de durée minimale est ACF de 16 mn
----------------------------------------------------------------------------------------------------------------------