>> They use something very different for routing. > > Then what is their algorithm? There a good chances that they use an approach similar to that one :
Precomputation: - Find 100 × 100 points in europe (that means a point every 30km) - Compute the distance between all those points and store it On request: - compute the shortest path to the nearest pre-computed node (dijkstra on a 30 by 30 km is not even a ms) on start and destination - you get an extreamly good approximation - use A* having this extra information. If your A* algorithm knows the exact distance to the destination, then it will run in O(n). Of course you can hack as much as you want arround that to improve the performances, but you get the idea. Finding the fastest route in less than a second in a desktop computer, is an easy task. The problem is finding a good route: avoiding to many changes, taking in account traffic lights, speed differences and so on. The other problem is on small devices with little memory (displaying the map is yet an other problem...) > Some would argue that the roads with highest importance tend to lie on > many shortest paths, i.e. the important highway was built for a > reason. Or how do you define importance? The problem is that we want a combination of shortest, fastest and most confortable route. The shortest we have the data. The fastest, we would need more data. The most confortable depends on every one. No real solution there. _______________________________________________ Routing mailing list [email protected] http://lists.openstreetmap.org/listinfo/routing
