Discussion :

[sasuma]

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.

[ToTo13]

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 .

[Garulfo]

Bonjour,

tout d'abord il te faudra donner une pondération à tes arrêtes : distances, ... ou tout simplement minimiser le nombre d'arrêtes.

Arrêtes avec ça !!
Un seul « r » siouplait

[sasuma]

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.

[ToTo13]

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.

[Hanz Peter Mariol]

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

[Hanz Peter Mariol]

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

[sasuma]

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

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

[pseudocode]

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...

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.