Bonjour à tous.
 
Voilà je chercherai un algo de dijkstra permettant de retrouver le plus petit chemin possible entre deux villes afin de réaliser une sorte de mappy.
Ca serait un mappy d'une centaine de ville mais bon si l'algo marche pour deux villes il peut bien marcher pour 100 :-)
 
Merci par avance car là je commence à m'arracher les cheveux.

Bein voila t'as tout dit    
L'algo de dijkstra s'appliquera bien vu la particularité d'un graphe correspondant à une carte routière, pour vérifier ce que j'avance je te laisse voir avec google parqu'il ne faut pas pousser non plus    

Ben implémente un dijkstra
 

bah je veux bien implementer un dijkstra mais je comprends rien à son algo...

 
Ah, et bien je vois que je ne suis pas le seul a galérer.
2 mois que je cherche a utiliser Dikjstra pour faire un "mappy" de quelques villes mais c'est à n'y rien comprendre.
 
Quelqu'un aurait-il un algo commenté par hasard ?
 
Merci par avance

je ne saurais trop vous conseiller de consulter ce bouquin : http://www.amazon.fr/exec/obidos/A [...] 50-8317755

 
le truc c'est que l'algo je connais, mais Dikjstra c'est bien chaud et je pense que pour faire un "mappy" c'est la meilleure solution, à moins que quelqu'un connaisse un autre type d'algo.
 
Je suis arrivé à un stade ou j'accepte n'importe quelle proposition...

Encore faut il avoir la "computer scientist attitude"
C'est loin d'être si chaud que ça, il suffit de commencer par étudier l'algo comme on le ferait avec un théorème de maths, avec un stylo et du papier; et de ne passer à l'implémentation que cette première étape franchie.

+1

http://www.koders.com/?s=dijkstra& [...] &la=*&li=*
youpie !

+2

Il suffit de faire une trace il y en a pour 20 min.

 
ben si tu pouvais faire une petite trace pour les noob comme moi par exemple car moi perso j'y arrive pas.
 
Merci de ton aide par avance

up

 
Pour 2 villes, je te le fais ton algo, mais c'est pas sûr qu'il marche pour 100    
 
 
Et sinon, tu as fais une recherche google ?
 
http://brassens.upmf-grenoble.fr/I [...] jkstra.htm
 
Pour une démo temps réel en java, suffit de cliquer sur "appliquette"...

 
Personnellement j'ai deja fait une recherche sur google et je suis tombé sur le meme site que toi. Il dechire j'avoue mais il est relativement incomprehensible pour moi.
 
Je repond à la place de Faboubou je veux bien que tu mettes ton algo pour 2 villes c'est toujours ca de pris et ca me permettra peut-être de mieux comprendre.
 
Merci d'avance

http://www.answers.com/shortest%20path%20problem
 
Il y a pas mal de resources pour chacune des techniques "classiques" (dijkstra, A*, etc.). A noter que pour ton problème, c'est plutôt A* qui m'a l'air approprié, vu que plutôt que de calculer tout le graphe, il vaut mieux prendre ce qui est intuitivement le chemin le plus court: la ligne droite.

up

pas mal la faute d'orthographe    
Que veux tu de plus à part m'énnerver?  

si jamais ça intéresse toujours quelqu'un j'ai fait il y a 2 ans un algorythme génétique pour résoudre le problème du voyageur de commerce (parcourir un certain nombre de villes en faisant le moins de kilomètre possible). Il est disponible sur le site codes source cpp (vous tapez "cppfrance pyronet voyageur" dans google vous pourrez télécharger ma source.
Le code est un peu bordélique j'avoue mais de souvenir assez bien commenté.
 
l'adresse exacte pour le googliste flemard :
http://www.cppfrance.com/codes/PRO [...] 27243.aspx