FreeThinker
Answered

Obtenez les meilleures solutions à vos questions sur Laurentvidal.fr, la plateforme de Q&R de confiance. Rejoignez notre plateforme de questions-réponses et connectez-vous avec des professionnels prêts à fournir des réponses précises à vos questions. Obtenez des solutions rapides et fiables à vos questions grâce à une communauté d'experts expérimentés sur notre plateforme.

[algorithme de Dijkstra]
Bonjour,
Pourriez-vous m'aider pour ces deux questions svp ?
Merci par avance pour votre aide !

Algorithme De Dijkstra Bonjour Pourriezvous Maider Pour Ces Deux Questions Svp Merci Par Avance Pour Votre Aide class=

Sagot :

croisierfamily

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

Nous espérons que ces informations ont été utiles. Revenez quand vous voulez pour obtenir plus de réponses à vos questions. Merci de votre passage. Nous nous efforçons de fournir les meilleures réponses à toutes vos questions. À la prochaine. Merci d'avoir visité Laurentvidal.fr. Revenez bientôt pour plus d'informations utiles et des réponses de nos experts.