Les graphes Dijkstra - Maths - Terminale - Les Bons Profs

un algorithme sur les graphes pour essayer de trouver le chemin le plus court qui existe entre le sommet a et le sommet G on a donc un graphe avec SEP sommet des arêtes des distances sur chaque sur chaque arête et on essaie donc de trouver quel est le chemin le plus court alors on peut trouver plein de chemins dans tous les sens il un nombre de combinaisons incroyabl mais l'algorithme de dixstra nous permet donc si on est assez rigoureux et assez on s'est bien entîn de trouver le chemin le le plus court d'une manière assez rapide alors l'algorithme de Dra ça se présente comme ça vous commencez par mettre dans l'ordre alphabétique tous vos sommets et puis au fur à mesure on va avancer donc je pars de a je vais jusqu'à g donc l'algorithme je vous l' rempl pour gagner un petit peu de temps je pars de a quand on est au sommet a on a trois possibilités où je vais en D ou je vais en C ou je vais en B avec les distances qu'il faut donc je vais en B j'ai fait 3 unités ou 3 m 3 cm on s'en moque en venant de a 6 pour aller à C 5 pour aller à D l'infini pour les autres je n'ai pas encore la je mets l'infini parce que je n'ai pas encore la distance pour aller de A à ces sommet là bien je prends toujours le la distance la plus courte parce que c'est ce qu'on cherche ici 3 6 et 5 donc je prends je choisis B ça veut dire que j'élimine maintenant le le somm B il est pris je considère donc que je suis à l'endroit où il y a B pour partir de B je vais parvenir à a j'ai donc deux possibilité où je vais en C ou je vais en D donc je viens de B où je vais en C j'étais en 3A je rajoute deux points pour aller en C donc je suis en 5 venant de B j'ai fait 5 unités venant de B ou j'ai fait 4 venant de venant de de B aussi pour aller au nombre d on vérifie 3 + 1 ça fait bien 4 venant de B d'accord je prends toujours le le chemin le plus court c'est 4B 4 venant de B c'est ça que ça veut dire je prends donc le sommet d j'élimine d au fur et à mesure je continue je suis en D je suis j'ai déjà pris A et B il me reste donc c E F G voilà pour aller de d bah j'ai deux possibilités je peux aller trois possibilités je peux aller à C je peux aller en e je peux aller à F donc je viens de d donc TR qure unités pour aller à C en venant de d 6 unités pour aller à E en venant de D et trois unités pour venir ici en F en venant de d bien le problème c'est qu'on arrive ici avec on a les le sommet ici qui vient de C on a une distance qui est plus courte que toute celle là donc je barre celle-là et je recopie le 5b c'està-dire que passer par d pour l'instant ça me plaît pas je repars de C je prends toujours la distance la plus courte d'accord même voilà celleelà elle est plus courte que tout le reste donc je repars de C je suis donc en C j'élimine le sommet C je repars de C j'ai j'ai je mets toutes mes possibilités venant de C comme d'habitude je regarde dans mon dans mon graphe les différentes distances j'ai ça j'ai donc ici la plus petite distance mais quand je regarde la ligne du dessus c'est 7D la ligne du dessus la plus petite distance d'accord vous voyez 14 9 7 c'est 7D donc je barre celle-là et je repars de F je repars de F ça veut dire que j'ai choisi F j'élimine F et je repars de F je suis en F jeux donc aller en E ou en G je rajoute mes deux distances je prends la plus petite le 9U c'est bien la plus petite de tout ce que j'ai se passe je prends e je suis en e et je rajoute ici un point pour aller à G donc je viens de je viens de e ça fait 10 e et à ce momentlà j'ai j'ai fini mon chemin je suis en G le chemin que je dois donc obtenir n'est pas la liste des des sommet que j'ai choisi mais il faut remonter toutes ces bulles donc vous partez de G je viens de E je vous ai fait le chemin en bas je suis arrivé en G je viens de e e voilà il vient d'ici le F vient de d d je viens de B et B je viens de a donc le chemin le plus court pour aller de A à G c'est A B D F E G et on a parcouru 10 unités 10 m 10 km 10 ce que vous voulez donc si vous êtes bien rigoureux faites attention de ne pas oublier les sommets qui sont au-dessus d'éliminer toutes les possibilités de de temps en temps on a besoin de revenir sur un sommet qui était au hasard voilà si on est bien rigourux et qu'on fait attention normalement il n'y a pas de problème pour faire ce ce chemin le plus court en utilisant l'algorithme de digin