We demonstrate how Dijkstra's algorithm for shortest path queries can be accelerated by using precomputed shortest path distances. Our approach allows a completely flexible tradeoff between query time and space consumption for precomputed distances. In particular, sublinear space is sufficient to give the search a strong “sense of direction”. We evaluate our approach experimentally using large, real-world road networks.
['Jens Maue', 'Peter Sanders', 'Domagoj Matijevic']
Goal-directed shortest-path queries using precomputed cluster distances