Demande d'un algorithme de plus court chemin
Fermé
liza
-
ami7 -
ami7 -
Bonjour tout le monde,
Est-ce que quelqu'un pourrait me dire quel algorithme je pourrais utiliser pour trouver un plus court chemin.
On m'a dit que je pouvais utiliser Dijkstra de manière récursive mais je ne vois pas comment.
Si vous avez de meilleures idées ou si vous pouvez tout simplement m'éclairer sur celle-là ça m'aiderait vraiment beaucoup.
Merci merci.
liza
Est-ce que quelqu'un pourrait me dire quel algorithme je pourrais utiliser pour trouver un plus court chemin.
On m'a dit que je pouvais utiliser Dijkstra de manière récursive mais je ne vois pas comment.
Si vous avez de meilleures idées ou si vous pouvez tout simplement m'éclairer sur celle-là ça m'aiderait vraiment beaucoup.
Merci merci.
liza
5 réponses
-
Salut,
Pas de récursivité, mais du vrai Dijkstra : attention le graphe ne doit pas
contenir de boucle.
http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra
Sinon y a Floyd, mais il manque d"efficacité sur les graphes important...
http://www.nimbustier.net/publications/djikstra/floyd.html
Ce site explique aussi Dijkstra...
A+, crabs-
Merci crabs
D'après ce que j'ai compris il faut faire un tableau à deux dimensions de taille nombre_de_positions * nombre_de_positions et ça me paraît énorme. Et je pense que si on pouvait caser une récursivité quelque part ça optimiserait un peu l'algo, non?
J'ai aussi entendu parler de l'algorithme A* mais apparemment il ne garantit pas de trouver le plus court chemin.
Qu'est-ce que tu en penses?
liza
-
-
Salut, un petite remarque en passant...
si on pouvait caser une récursivité quelque part ça optimiserait un peu l'algo
Ca pas vraiment, quand tu cherches à caser une récursivité en force tu fais plus de mal que de bien :)
-
Salut,
Là je suis en parfait accord avec teebo.
Maintenant si tu réfléchis un peu, un graphe avec 100 noeud ça te prendra
moins d' 1 Mo.
Dijkstra, c'est l'algo retenu pour le routage à la place de RIP, et il est très
certainement le plus efficace.
Sinon l'algo A-star c'est surtout pour les labyrinthes, il part du principe qu'il
faut s'approcher de la sortie.
A+, crabs-
Bonjour,
En fait c'est un projet que j'ai à faire. J'ai une matrice de taille 26*26 et je dois trouver (comme tu l'as déjà compris j'imagine) le plus court chemin entre deux positions (déterminées) dans la matrice.
Au départ je pensais représenter les positions de la matrice par un tableau et le parcourir en largeur mais ça m'a l'air drôlement compliqué.
Pour Dijkstra, le problème est que je n'ai jamais étudié les graphes et je ne comprends pas bien les algorithmes que j'ai lu sur le net.
Quand on est à une position donnée (par exemple au départ), comment est-ce que je choisis vers quelle direction aller en premier sachant qu'une arrête entre 2 positions a toujours une valeur de 1. Ou alors, à chaque position, comment traiter tous les successeurs en même temps?
Ça fait beaucoup de questions je sais mais en faite je suis assez perdue avec cet algorithme.
Merci de m'aider.
liza -
C'est pas nécessairement un cas typique et il n'y a pas 1 plus court chemin (sauf cas particuliers) mais plusieurs...
Tu as le droit aux diagonales ou pas?
Dans le cas ou ta réponse est non:
Calcul Dx et Dy, si un des deux est nul=> la solution est immédiate plus besoin de faire des calculs savant
Sinon tu avances te déplaces d'abord sur un axe et ensuite sur l'autre, pas besoin de chercher un optimum, tant que tu te déplaces dans le bon sens sans aller trop loin tu seras sur un des plus courts chemins...
Si tu as le droit aux diagonales, c'est plus compliqué (sauf dans le cas ou les deux sont sur une même ligne (Dy=0) ou une même colonne (Dx=0) où là la solution est encore une fois immédiate...
Mais dans l'absolu il faut que tu te déplaces dans la diagonale vers ton point d'arrivée autant de fois que le plus petit de tes deux D puis après sur l'autre axe du nombre de fois restant, pas bien compliqué tout ça, rien à voir avec un parcours d'arbre :)
- Merci teebo
Arggg!! J'ai oublié de préciser certaines choses je crois. Je dois coder un genre de sokoban en mode automatique avec une caisse et des murs à l'intérieur de l'aire de jeu.
Ça complique un peu les choses. Javais pensé aux distances un moment mais il est possible qu'à cause des murs il faille provisoirement éloigner le bonhomme et la caisse de la cible.
Donc je ne peux pas savoir à l'avance quel chemin je vais utiliser.
-
-
voilà un site qui va t'aider qui donne de l'assistance sur un projet comme le tien sur les graphe tu dois le visité
www.easytools.zoneforum.com -
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question -
salut,
moi aussi je cherche des algorithmes de calcul de plus courts chemin j'ai trouvé l'algorithme de Malgrange
il doit considére les contraintes suivants:
-le graphe doit etre non orienté connexe
-l'algorithme ne prend pas en compte la notion de poids
-le plus court chemin doit etre elementair
-les chemin ne contienne pas de circuit absorbant
