Opened 13 years ago

Closed 12 years ago

#261 closed defect/bug (invalid)

Faster routing

Reported by: Darhuuk Owned by: KaZeR
Priority: major Milestone: want patch / contribution
Component: core Version: git master
Severity: 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 (2)

comment:1 in reply to: ↑ description Changed 13 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 12 years ago by KaZeR

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

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.