Trouver son chemin dans le métro - Page 1

http://www.subwaynavigator.com

Comment marche en gros un algorithme de ce genre, et quelle est la meilleur façon de stocker la base de données des lignes et des stations?

Peut-être qu'il utilise Dijkstra...
Je crois que c'est un algo assez adapté à ce type de pb.

ExtendeD a écrit :
http://www.subwaynavigator.com
Comment marche en gros un algorithme de ce genre, et quelle est la meilleur façon de stocker la base de données des lignes et des stations?

Recherche de plus court chemin (Dijkstra, Floyd, Bellman, A*, ...) sur un graphe orienté (stocké sous forme de listes d'adjacence) ptet ?

cad "de listes adjacentes" ?

moi je vote dijkstra et utilisation de graphes.
regarde rapidement dans topics/13052-probleme-du-postier et si tu veux le rapport algo qu'on avait redigé... y'a po de probleme
ps : y'a des plus court chemin

ExtendeD
a écrit : cad "de listes adjacentes" ?

Pour chaque sommet tu as une liste de successeurs... c'est beaucoup moins gourmand en mémoire que les matrices d'adjacence, surtout pour des gros graphes.

J'ai un copain qui en avait fais un, mais pb, c que son prog pouvait des trajets très long. Depuis je ne sais ce qu'est devenu son prog

C'est cool ce site!

y'a un prog qui fait ça sur HP, et vite

oué c vrai que c interessant ce genre de programme

je cherche pareil l'algoryhtme.y a un prog ki s'appelle métro sur pocket pc et qui fait ca trè bien je sais po si la source est dispo.G déjà essayé de fiare une méthode de tri avec 5 destinations et ca foirait déjà

Ben sur le site de la ratp c encore mieux ...
Ca fait ca avec des adresses et pas des stations...
Ca pondère les temps de trajet avec les distance station-adresse...