Robust, almost constant time shortest-path queries in road networks
Peter W. Sanders, Dominik Schultes · DIMACS series in discrete mathematics and theoretical computer science · 2009
When you drive to somewhere ‘far away’, you will leave your current location via one of only a few ‘important’ traffic junctions. Starting from this informal observation, we develop a generic algorithmic approach—transit node routing—that allows us to reduce quickest-path queries in road networks to a small number of table look-ups. We implement this basic approach using highway hierarchies. For the road maps of Western Europe and the United States, our best query times improve over the best previously published figures by two orders of magnitude. This is more than one million times faster than the best known algorithm for general networks. We also explain how to compute complete descriptions of shortest paths (and not only their lengths) very efficiently.