Si le but est de faire un calcul d’itinéaire point à point, il y a considérablement plus performant que ce genre de vieilleries (on parle de plusieurs facteurs 1000) : on peut calcul un trajet sur les routes de n’importe quel point de la planète à n’importe que point en une milliseconde sur un desktop. Le plus lent est de générer le flux de sortie :)
La grande différence c’est que dans le cas de Navitia, il cherche tous les arrêts à ~15 min de marche (paramétrable bien sur) et envisage cet arrêt comme point de départ. Il faut donc une recherche concentrique autour du point de départ, là où une heuristique vise juste à éviter d’étudier ce qu’il y a à gauche si on veut aller à droite.
Il y a une deuxième différence : le rayon de recherche est très restreint. On parle de 5 km à vélo, à la rigeur 20km en voiture, jamais de trajet qui traverse la France.
La performance du composant Dijkstra n’est donc absolument pas un problème et la simplicité du code prévaut :)
[^] # Re: Dijkstra ?
Posté par Tristramg . En réponse à la dépêche Libération de navitia : un calculateur d’itinéraire pour les transports en communs. Évalué à 4.
Si le but est de faire un calcul d’itinéaire point à point, il y a considérablement plus performant que ce genre de vieilleries (on parle de plusieurs facteurs 1000) : on peut calcul un trajet sur les routes de n’importe quel point de la planète à n’importe que point en une milliseconde sur un desktop. Le plus lent est de générer le flux de sortie :)
J’avais tenté de vulgarisé un peu ce qui s’est fait dans un article de blog : http://blog.tristramg.eu/petit-historique-du-calcul-ditineraire.html
La grande différence c’est que dans le cas de Navitia, il cherche tous les arrêts à ~15 min de marche (paramétrable bien sur) et envisage cet arrêt comme point de départ. Il faut donc une recherche concentrique autour du point de départ, là où une heuristique vise juste à éviter d’étudier ce qu’il y a à gauche si on veut aller à droite.
Il y a une deuxième différence : le rayon de recherche est très restreint. On parle de 5 km à vélo, à la rigeur 20km en voiture, jamais de trajet qui traverse la France.
La performance du composant Dijkstra n’est donc absolument pas un problème et la simplicité du code prévaut :)