Changes between Initial Version and Version 1 of Ticket #261


Ignore:
Timestamp:
11/01/08 22:13:32 (12 years ago)
Author:
Zaxl
Comment:

Replying to Darhuuk:

I read in the manual that Navit uses Dijkstra's algorithm for routing. This could be made (potentially a lot) faster by using the A* algorithm instead (http://en.wikipedia.org/wiki/A-star). Making necessary changes to the source probably won't take more than 2 minutes for a very simple h(x) (only the cost/distance function needs to be changed).

Easiest would be to implement h(x) as straight distance to destination, maybe max speed allowed on the road that's being checked could be in some way incorporated as well (but I don't know if this information is available in Navit), but then you need to be sure h(x) still is admissible (no overestimation of actual distance, for more info see the pretty decent Wikipedia explanation).

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #261 – Description

    initial v1  
    1 I read in the manual that Navit uses Dijkstra's algorithm for routing. This could be made (potentially a lot) faster by using the A* algorithm instead (http://en.wikipedia.org/wiki/A-star). Making necessary changes to the source probably won't take more than 2 minutes for a very simple h(x) (only the cost/distance function needs to be changed).
     1Hi,
    22
    3 Easiest would be to implement h(x) as straight distance to destination, maybe max speed allowed on the road that's being checked could be in some way incorporated as well (but I don't know if this information is available in Navit), but then you need to be sure h(x) still is admissible (no overestimation of actual distance, for more info see the pretty decent Wikipedia explanation).
     3Current routing is not slow due to djikistra.
     4And it's definitely no 2 minute change to fix that.
     5Patches welcome :)