Ticket #261 (closed defect/bug: invalid)

Opened 3 years ago

Last modified 3 years ago

Faster routing

Reported by: Darhuuk Owned by: KaZeR
Priority: major Milestone: want patch / contribution
Component: core Version: svn
Keywords: Cc:

Description (last modified by Zaxl) (diff)

Hi,

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

Change History

comment:1 in reply to: ↑ description Changed 3 years ago by Zaxl

  • Description modified (diff)

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

comment:2 Changed 3 years ago by KaZeR

  • Status changed from new to closed
  • Resolution set to invalid
  • Milestone set to want patch / contribution

We are constantly working on improving performances. For a subject as important as this one, it would be better to have a chat with us in #navit. i have to close this ticket, there is no quick fix, and performances of routing is of course one of the top priority subject.

Note: See TracTickets for help on using tickets.