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