[Navit-users] [PATCH] A* search for navit, nice speedup in many cases

[<hel...@ai...>]

A patch that makes navit routing use the A* search algorithm. The patch is
small because A* is nearly the same as the Dijkstra algorithm already
implemented.

My speed test:
1. Load a OSM map of Scandinavia
2. Have navit find a route from Trondheim to Copenhagen.
   (Navit will search from Copenhagen to Trondheim.)

The Dijkstra algorithm used 8s on my work laptop.
The A* algorithm uses 2s. :-)  4x speedup for this case.

Strangely enough, I am completely unable to reproduce the old test. All
versions of navit (dijkstra, A*) now does this route in 2s.

I am very irritated at the moment. There could still be a bug in my code
that prevents A* from being faster than dijkstra. No problem with that.
This does *not* explain why the old program used to use 8s and now
suddenly use 2s though. Looks like the world is not behaving realistic
today, which is nasty.

I hope someone interested will test the patch and see if it makes any
difference.