le calcul routier est simplement l’implémentation de l’algorithme de Dijsktra par Boost::Graph.
Sauf erreur de ma part, dans un graphe avec des coordonnées euclidienne, l'algorithme de Sedgewick et Vitter est bien
plus efficace car il introduit une heuristique:
Il y a quelques années (houla, avec l'implémentation que j'en avais faite en C et qui tournait sur un SIG extrait des données d'un fournisseur dont l'effigie est un "bonhomme", il n'y avait pas photo.
(Je pourrais même la ressortir si ça peut servir ;-)
# Dijkstra ?
Posté par El Titi . En réponse à la dépêche Libération de navitia : un calculateur d’itinéraire pour les transports en communs. Évalué à 4.
le calcul routier est simplement l’implémentation de l’algorithme de Dijsktra par Boost::Graph.
Sauf erreur de ma part, dans un graphe avec des coordonnées euclidienne, l'algorithme de Sedgewick et Vitter est bien
plus efficace car il introduit une heuristique:
http://archive.numdam.org/ARCHIVE/RO/RO_1996__30_4/RO_1996__30_4_333_0/RO_1996__30_4_333_0.pdf
Il y a quelques années (houla, avec l'implémentation que j'en avais faite en C et qui tournait sur un SIG extrait des données d'un fournisseur dont l'effigie est un "bonhomme", il n'y avait pas photo.
(Je pourrais même la ressortir si ça peut servir ;-)
Je conseille d'ailleurs la lecture de cet excellent ouvrage:
http://livre.fnac.com/a1467137/Philippe-Lacomme-Algorithmes-de-graphes#ficheResume