On Dijkstra's Algorithm

Re:On Dijkstra's Algorithm by michaelt on Tuesday April 21, 2015 @06:21AM (#9413112)

Nowerdays, Google Maps is most likely using more modern algorithms, like 'contraction hierarchies' [1] - the algorithm inserts shortcuts into the graph in a structured way, so you only switch from a higher-numbered shortcut to a lower-numbered shortcut (or non-shortcut) at the very start or end of the route. This radically reduces the number of edges that need to be explored.

[1] https://www.youtube.com/watch?v=-0ErpE8tQbw

[ Parent | on HN ]

Re:On Dijkstra's Algorithm by lorenzhs on Tuesday April 21, 2015 @06:51AM (#9413199)

Calling Contraction Hierarchies 'a variation' of Dijstra's algorithm, as the article does, is a bit of an understatement though.

For anyone interested in route planning algorithms, there is a wide variety of interesting speed-up techniques. Some more key words: Arc Flags, Landmarks, Multi-Layer Dijkstra, Customizable Route Planning, Hub Labelling, Highway Hierarchies, PHAST. For transportation networks, also have a look at RAPTOR. A list of interesting references is available at http://i11www.iti.uni-karlsruhe.de/teaching/sommer2014/route... (the slides are in German, unfortunately)

[ Parent | on HN ]

Re:On Dijkstra's Algorithm by amelius on Tuesday April 21, 2015 @06:50AM (#9413196)

A hierarchical approach makes a lot of sense, intuitively. It makes me wonder why it took so long before such method was considered.

[ Parent | on HN ]

Re:On Dijkstra's Algorithm by lorenzhs on Tuesday April 21, 2015 @06:53AM (#9413206)

The area of route planning research got a large boost with the 9th DIMACS Implementation challenge in 2005/06, this is where most of the research into fast and exact route planning algorithms started. (What sat nav vendors did and are still doing usually isn't exact, they were using inexact heuristics that were based on the 'natural' hierarchy in the road network)

[ Parent | on HN ]