Version imprimable
Bonjour,
j'ai un graphe qui comporte des sommets et chaque 2 sommets sont reliés par une arête. Une aretê peut être positif ou nulle (par exp un sens interdit entre 2 rues donc je ne peux pas passer par ce chemin...).
Je veux faire un algorithme qui détermine le chemin le plus court qui part d'un sommet A vers un sommet B.
est ce que quelqu'un pourra m'aider dans cet algo SVP
merci d'avance.
Bonjour,
tout d'abord il te faudra donner une pondération à tes arêtes : distances, ... ou tout simplement minimiser le nombre d'arêtes.
Sinon l'algorithme que tu cherches est sans aucun doute l'algorithme de Dijkstra.
Tu trouveras de la documentation et des discussions détaillées dans le forum, ainsi qu'une documentation surabondante sur :google:.
Arrêtes avec ça !! :mrgreen:Citation:
Envoyé par ToTo13
Un seul « r » siouplait ;)
http://fr.wikipedia.org/wiki/Algorithme_de_dijkstra
dans ce lien ci-dessus, il y a une explication détaillée de l'algo de dijkstra, je comprend des choses mais y en a ceux que je comprend pas!!
en bas de la page y a un exemple pour trouver le plus court chemin en partant de francfort pour arriver à Munich: ce que je comprend pas comment qd il est arrivé à Karlsruhe avec 165 km, ca sert à koi de revenir passer par kassel dont la distance par rapport à francfort fait 173 km vu que 165 < 173 donc pourquoi il reviens passer par kassel au lien de continuer vers le nœud la ville relié a Karlsruhe qui est Augsburg...
est ce que quelqu'un pourra m'expliquer comment ça marche l'algo si c'est possible à travers cet exemple SVP !
merci d'avance.
Bonjour,
c'est pas qu'il revient en arrière à proprement parlé, mais il doit connaître toutes les possibilités, TOUTES.
Donc il doit tester tous les chemins possibles afin de trouver le plus cours.
Donc dans la façon de faire de l'algorithme tu as l'impression qu'il revient en arrière, mais en fait c'est juste que la recherche ce fait de cette façon.
Tu ne t'es pas posé la question, pourquoi va-t-il passer par wurzburg (217), alors que mannheim est à 85?
Tu devrais recherché les différence entre les algorithmes de théorie des graphs DFS et BFS. L'un consiste à trouver le chemin en parcourant toutes les possibilité dans la profondeur de l'arbre, l'autre en parcourant toutes les possibilités dans la largeur.
Ici nous parcourons dans la largeur. Au final le but est de trouver le chemin le plus court, donc si on ne parcours pas toutes les possibilités, comment peut on être sur que nous avons la réponse optimale?
Ainsi à l'étape 1, il regarde tous les premiers noeuds auquel il peut accéder. A la suivante, tous ceux qu'il peut atteindre à partir des premiers, et ainsi de suite. et ce n'est qu'en sommant les poids de chaque arcs parcouru qu'on obtient la longueur du chemin.
Si tu regardes bien le plus court chemin au final est würz - nürn - münchen. Donc pas du tout celui qu'on aurait pu imaginer en se basant sur la premiere itération.
D'ou l'utilité de parcourir tous les chemin d'une manière ou d'une autre,
J'espère avoir compris ta question et y avoir répondu,
Bonne journée
Parceque Aufgsburg est à 415km de Frankfurt, alors que Kassel n'est qu'à 173 km de Frankfurt. A cet étape de l'algorithme, il est donc plus interessant de regarder du coté de Kassel que de Aufgsburg. ;)Citation:
Envoyé par sasuma
Je me reprend, on ne peut pas vraiment qualifier dikjtra de bfs^^. Cela étant l'étude de BFS et DFS aide pas mal a la compréhension des autres algo en theorie des graphs
Citation:
Envoyé par Hanz Peter Mariol
ah oui d'acord!! la je comprend mieux:)
donc ce n'est pas question qu'il revienne mais c juste qu'il dois tester ts les chemins possible en essayant de trouver le plus court!!!
merci
encore dans le lien http://fr.wikipedia.org/wiki/Algorithme_de_dijkstra
L'algorithme de dijkstra utilise plusieurs fonctions, parmi ces fonctions on trouve:
Mise à jour des distances
* On met à jour des distances entre sdeb et s1 en se posant la question : vaut-il mieux passer par s2 ou pas ?
maj_distances(s1,s2)
si d[s2] > d[s1] + Poids(s1,s2)
alors d[s2] := d[s1] + Poids(s1,s2)
prédécesseur[s2] := s1 /* on fait passer le chemin par s2 */
ici apparemment on compare la distance entre le point de départ sdeb et le nœud S2 avec celle entre sdeb et S1.
normalement si d[S2] > d[S1] sachant que s2 est situé après S1, dans ce cas on passe par S1 vu que c plus proche, mais ici je voit qu on passe par S2. c est ça que je comprend pas!!
est ce que quelqu'un pourra m expliquer cette fonction SVP!
merci encore et bon weekend
Bonjour,
en testant les différents chemin, tout en travaillant toujours sur le plus court, il est parfois possible qu'il existe plusieurs chemin pour arriver à un nœud. Il faut alors savoir quel est le chemin le plus court.
Donc dans le cas que tu présentes, on arrive à S2, en passant par S1. Donc si la plus courte distance trouvée jusqu'alors entre Sdeb et S2 est inférieure à la plus courte distance trouvée entre Sdeb et S1 plus la distance entre S1 et S2, cela ne sert à rien de passer pour S1 pour aller à S2. Dans le cas contraire (au cas où c'est plus court), on met à jour la distance entre Sdeb et S2, puis on dit que le prédécesseur de S2 est S1, car le plus court chemin entre Sdeb et S2 passe maintenant par S1.