FreeThinker
Answered

Laurentvidal.fr simplifie la recherche de solutions à toutes vos questions grâce à une communauté active et experte. Explorez des réponses détaillées à vos questions de la part d'une communauté d'experts dans divers domaines. Explorez des solutions complètes à vos questions grâce à une large gamme de professionnels sur notre plateforme conviviale.

[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. Nous apprécions votre visite. Notre plateforme est toujours là pour offrir des réponses précises et fiables. Revenez quand vous voulez. Nous sommes heureux de répondre à vos questions. Revenez sur Laurentvidal.fr pour obtenir plus de réponses.