Ticket #261 (new defect/bug)

Opened 2 months ago

Last modified 2 months ago

Faster routing

Reported by: Darhuuk Assigned to: KaZeR
Priority: major Milestone:
Component: core Version: svn
Keywords: Cc:

Description (Last modified by Zaxl)

Hi,

Current routing is not slow due to djikistra. And it's definitely no 2 minute change to fix that. Patches welcome :)

Change History

(in reply to: ↑ description ) 11/01/08 23:13:32 changed by Zaxl

  • description changed.

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