Lors d&rsquo une campagne électorale, un homme politique doit effectuer une tournée dans les villes A, B, C, D, E, F, G et H, en utilisant le réseau autoroutier. Le graphe ci-dessous représente les différentes villes de la tournée et les tronçons d&rsquo autoroute reliant ces villes (une ville est représentée par un sommet, un tronçon d&rsquo autoroute par une arête) :

a) complet  (0,5 point)

b) connexe. (0,5 point)

b) Citer un trajet de ce type. (0,5 point)

a) Déterminer la matrice . (0,5 point)

b) On donne la matrice .

Déterminer, en justifiant, le nombre de chemins de longueur 3 reliant E à H.

Préciser ces chemins. (1 point)

Des contraintes d&rsquo organisation obligent cet homme politique à se rendre dans la ville F après la ville A.

Le graphe est complété ci-dessous par les longueurs en kilomètre de chaque tronçon d&rsquo autoroute.

Déterminer, en utilisant l&rsquo algorithme de Dijkstra, le trajet autoroutier le plus court pour aller de A à F. Préciser la longueur en kilomètre de ce trajet. (1,25 point)