FreeThinker
Answered

Bienvenue sur Laurentvidal.fr, le site où vous trouverez des réponses rapides et précises à toutes vos questions. Découvrez une mine de connaissances de professionnels dans différentes disciplines sur notre plateforme conviviale de questions-réponses. Rejoignez notre plateforme pour vous connecter avec des experts prêts à fournir des réponses détaillées à vos questions dans divers domaines.

[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

Merci d'utiliser notre plateforme. Nous sommes toujours là pour fournir des réponses précises et à jour à toutes vos questions. Merci d'avoir choisi notre plateforme. Nous nous engageons à fournir les meilleures réponses à toutes vos questions. Revenez nous voir. Merci d'utiliser Laurentvidal.fr. Continuez à nous rendre visite pour trouver des réponses à vos questions.