We consider the point-to-point (approximate) shortest-path query problem, which is the
following generalization of the classical single-source (SSSP) and all-pairs shortest-path …

We survey recent advances in algorithms for route planning in transportation networks. For
road networks, we show that one can compute driving directions in milliseconds or less even …

We present a route planning technique solely based on the concept of node contraction. The
nodes are first ordered by 'importance'. A hierarchy is then generated by iteratively …

Contraction hierarchies are a simple approach for fast routing in road networks. Our
algorithm calculates exact shortest paths and handles road networks of whole continents …

Algorithms for route planning in transportation networks have recently undergone a rapid
development, leading to methods that are up to three million times faster than Dijkstra's …

Efficient fastest path computation in the presence of varying speed conditions on a large
scale road network is an essential problem in modern navigation systems. Factors affecting …

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 an …

During recent years, impressive speed-up techniques for Dijkstra's have been developed.
Unfortunately, the most advanced techniques use bidirectional search, which makes it hard …

Abstract In [1], we presented a shortest path algorithm that allows fast point-to-point queries
in graphs using preprocessed data. Here, we give an extensive revision of our method. It …

In recent years, highly effective hierarchical and goal-directed speed-up techniques for
routing in large road networks have been developed. This article makes a systematic study …