Réponse :
Explications étape par étape :
■ tableau-résumé des trajets les plus courts :
départ = ville 4
arrivée --> 1 2 3 5 6 7
durée --> 4 3 2 2 5* 4** heures
* de 4 à la ville 6 en passant par 5
** de 4 à 7 en passant par 3
■ tableau de Dijkstra :
durée du trajet le plus court en gras ! ☺
départ --> 1 2 3 4 5 6 7 arrivée↓
0 2 6 4 6 1o 6 1
2 0 4 3 5 8 4 2
6 4 0 2 4 5 2 3
4 3 2 0 2 5 4 4
6 5 4 2 0 3 6 5
1o 8 5 5 3 0 7 6
6 4 2 4 6 7 0 7
remarque :
comme l' aller ou le retour durent le même temps en heures,
il y a symétrie par rapport à la diagonale des zéros,
on constate qu' il y a seulement 21 chemins "les plus courts" !
( 7² - 7 ) / 2 = ( 49 - 7 ) / 2 = 42 / 2 = 21
