[Routing] Yet another parser

[Dennis Luxen]

[A* bad snipped]

> 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.

Yes, it is common. But I have several reasons not to use it at all. One 
of these reason is that hacking does not yield any algorithmic advantages.

> The performances of A* strongly depends on the heuristic.

ACK. But the method itself is limited.

> 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.

I am not sure what you try to say with that. My point is that that there 
are completely different methods from A* that perform _very_ well and 
that are faster by the order of magnitudes. For example, consider the 
method called "Transit Node Routing". It is possible to compute a 
shortest path in two or three microseconds, IIRC.

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

There is paper that reports on speedup techniques and various 
combinations: https://algo2.iti.uni-karlsruhe.de/1328.php. Page 19 lists 
preprocessing and query times for various methods.

--Dennis