Graphe pondéré : plus court chemin par l'algorithme de Dijkstra

Un réseau routier relie cinq villes A, B, C, D et E. Le graphe est non orienté et pondéré : chaque arête porte un poids égal à la durée du trajet, en minutes. Les liaisons sont :

$A-B$ : $2$ ; $A-C$ : $5$ ; $B-C$ : $2$ ; $B-D$ : $4$ ; $C-D$ : $1$ ; $C-E$ : $7$ ; $D-E$ : $3$.

On souhaite déterminer le trajet le plus rapide de la ville $A$ à la ville $E$.

1. Écrire la matrice des poids $W$ de ce graphe (ordre $A,B,C,D,E$), en plaçant un $0$ sur la diagonale et le symbole $\infty$ lorsqu'il n'y a pas d'arête directe.

2. En appliquant l'algorithme de Dijkstra à partir du sommet $A$, déterminer la plus courte distance de $A$ à chacune des autres villes.

3. En déduire la durée minimale du trajet de $A$ à $E$, ainsi que l'itinéraire correspondant.

4. Le trajet direct le plus court en nombre d'arêtes (par exemple $A-C-E$) est-il aussi le plus rapide ? Commenter.