Fast Route Planning
Why Stack Overflow recommends it
Stack Overflow users link it in answers about how map services compute directions, as an accessible introduction to contraction hierarchies and related speed-up techniques.
Recommended by 3 people across 4 different months, 2010 to 2018.
What it is
A 2009 Google Tech Talk by Peter Sanders on fast route planning in continent-sized road networks. He covers contraction hierarchies, transit-node routing and distance tables, then extensions to turn penalties, traffic, time-dependent weights and public transport.
Cited in 1 Wikipedia article, including Shortest path problem.
What people said
Recommends SebastianK · 2010-08 · Stack Overflow · on “What algorithms compute directions from point A to point B on a map?”
In particular Contraction Hierarchies. You can find more about it here: [LINK] There is also a google tech talk about it: [this video]
Recommends eikes · 2010-10 · Stack Overflow · on “What algorithms compute directions from point A to point B on a map?”
Here's the world's fastest routing algorithms compared and proven for correctness: [LINK] Here's a google tech talk on the subject: [this video] Here's a implementation of the highway-hierarchies algorithm as discussed by schultes (currently in berlin only, I'm writing the interface and a mobile version is being developed as well): [LINK]
Recommends Barnaby Hussey-Yeo · 2014-05 · Stack Overflow · on “Which algorithm does Google maps use to compute the direction between 2 points?”
To the best of my knowledge Google has never publicly stated which algorithm it uses of P2P queries. Although the current state of the art from the literature in terms of query times is the Hub labelling algorithm proposed by Abraham et al. [LINK] . A through and excellently written survey of the field was recently published as a Microsoft technical report [LINK] . The short version is... The Hub labelling algorithm provides the fastest queries for static road networks but requires a large amount of ram to run (18 GiB). Transit node routing is slightly slower, although, it only requires around 2 GiB of memory and has a quicker preprocessing time. Contraction Hierarchies provide a nice trade
Recommends Barnaby Hussey-Yeo · 2014-08 · Stack Overflow · on “What algorithms compute directions from point A to point B on a map?”
The current state of the art in terms of query times for static road networks is the Hub labelling algorithm proposed by Abraham et al. [LINK] . A through and excellently written survey of the field was recently published as a Microsoft technical report [LINK] . The short version is... The Hub labelling algorithm provides the fastest queries for static road networks but requires a large amount of ram to run (18 GiB). Transit node routing is slightly slower, although, it only requires around 2 GiB of memory and has a quicker preprocessing time. Contraction Hierarchies provide a nice trade off between quick preprocessing times, low space requirements (0.4 GiB) and fast query times. No one algo
Cites ashleedawg · 2018-02 · Stack Overflow · on “offline GTFS connection from A to B”
If you just want to dynamically calculate shortest travel routes between static hubs, in an offline application, determined like the following image, you can use the following formula: [LINK] [LINK] ( Source [LINK] ) Here's the pseudo code: 1 function Dijkstra(Graph, source): 2 3 create vertex set Q 4 5 for each vertex v in Graph: // Initialization 6 dist[v] ← INFINITY // Unknown distance from source to v 7 prev[v] ← UNDEFINED // Previous node in optimal path from source 8 add v to Q // All nodes initially in Q (unvisited nodes) 9 10 dist[source] ← 0 // Distance from source to source 11 12 while Q is not empty: 13 u ← vertex in Q with min dist[u] // Node with the least distance 14 // will be