A la recherche d'un algorithme ...

[invite0f31cf4c]

... Pour m'aider à developper une application.

Bonsoir à tous ... Je ne sais pas trop si je dois poster ce message dans la catégorie Maths ou dans la catégorie informatique ... Mais je pense que c'est tout de même ici que c'est le plus approprié étant donné que l'on ne va pas parler de programmation.

Alors voilà ... Je suis en train d'essayer de developper un petit logiciel qui permet d'aider à faire ses trajets dans le metro. Grosso modo, le programme prend comme paramètre la station de départ et la station d'arrivée, et en sortie, on nous donne le chemin le mieux, avec les arrêts et tout ce qu'il faut faire.

Sauf que voilà. Pour tout ce qui est de la modélisation du métro et tout ça ... Pas de soucis. Mais je galère pour trouver le meilleur chemin ... Et c'est là que j'ai besoin de votre aide.

Je sais qu'il existe déjà plusieurs algos, comme celui de Ford ou celui de Djousktra (Hum ... Désolé pour l'orthographe ...), mais même si c'est cela qu'il faut utiliser, je ne vois pas comment. Donc si quelqu'un peut m'aider ...

Merci beaucoup !
++ !
L.S.
-----

[invite3d7be5ae]

Le métro, c'est un graphe non?
Tu peux donc appliquer l'algorithme de Djikstra : http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra.
Sinon, tu peux faire de la récursivité.
Pour cela, tu dis que la distance d'un point (fixe) à un autre, c'est le minimum des distances des points autours+1.
La distance du point fixé à lui-même est évidemment 0.
Tu dois noter les points où tu es déjà passé pour éviter de tourner en rond et vérifer pour prendre la distance que tu n'est pas déjà passé par là.
Après, tu prend comme point fixe le point de départ (où d'arrivée, au choix) et tu appliques l'algorithme avec l'autre point.

En espérant t'avoir aidé,Pole.

[invite0f31cf4c]

Merci pour ta réponse !
Alors pour l'agorithme de Dijkstra, c'est mort. En effet, le graph que j'utilise n'est pas orienté, et la condition pour pouvoir utiliser cet algorithme est d'avoir un graph orienté.
Et pour le coup des appels reccursifs ... Bah je vais essayer. Mais ça risque d'être un peu plus compliqué à mettre en place et je ne sais pas trop encore comment je vais faire ça .
Donc si quelqu'un à une autre solution ... N'hesitez pas !
++ !
L.S.

[spi100]

Dijkstra c'est une bonne idée, si ton réseau n'est pas trop gros. Sinon un algorithme basé sur une heuristique comme le A* sera plus efficace. Dans ton cas, l'heuristique sera la distance à vol d'oiseau entre le point de départ et le but.

C'est assez simple à implémenter, le lien suivant http://fr.wikipedia.org/wiki/Algorithme_A%2A
te donne les détails et le pseudo code.

[A voir en vidéo sur Futura]

[invite914a6080]

En même temps, pour passer d'un graph non orienté à un graph orienté, il suffit de doubler les arrêtes de ce graph (un arc dans un sens et un arc dans l'autre pour chaque arrete non orienté si le métro peut aller dans les deux sens)