[Routing] Yet another parser

[Tristram Gräbener]

> I don't think so. A* and related algorithms are too slow for large road
> networks of entire continents. Even hacking doesn't help to overcome
> that performance barrier. And still A* is a heuristic algorithm. It can
> perform arbitrarily bad. And correct me if I'm wrong, but didn't the
> algorithm you describe come from MS Research? That would be another
> reason for Google not to use it.

The approach I described seems to be a common base to compute the
shortest path. Then you can hack arround as much as you want.

The performances of A* strongly depends on the heuristic.
If you have THE perfect heuristic that knows exactly the smallest
*distance* to the destination, then the A* will iterate only the nodes
of the shortest path. As anyway you will have to list those nodes at
some point (to render the path for example), it's impossible to have a
better algorithm. If you have the shortest path stored somewhere, then
improvement would be better only by a constant factor.

That approch tries to get an almost perfect estimation of the distance
to the destination and it's quite hard to trick.

The europe OSM map has arround 10M nodes I guess (in the node-edge
sense, not in the OSM sense). I only I weren't that lasy to implement
it to have a better idea of how it really performs...