> Ok, you're right. There a much better solutions. But even the worst > solutions take less than a second, even simplistic ones like an A* > with an improved heuristic. > > And we loop back to my intial point: computing the shortest path > accross europe, is no big deal on a desktop computer ;)
A single shortest path has never been much of a problem for a current desktop computer as long as the RAM suffices. A plain dijkstra implementation will take something like 4 or 5 seconds for any query within europe. But only if you do it once and don't care for memory consumption during the computation. The number of settled nodes that the algorithm inspects can be large. On the other hand consider a server scenario, i.e. some online routing planning thing. Further assume that the routing data structure fits into RAM and you can answer any query in 0.2 miliseconds, that is 5.000 requests each second. And that wouldn't involve any fancy hardware, but some standard PC. So, that would give you something like few hundred million requests that you can answer each day without hassle. Now let's add overhead for communication and such. Let's say we can still answer 100 million requests each day on a standard PC. -Dennis _______________________________________________ Routing mailing list [email protected] http://lists.openstreetmap.org/listinfo/routing
