Goal-directed shortest-path queries using precomputed cluster distances
Jens Maue, Peter W. Sanders, Domagoj Matijević · ACM Journal of Experimental Algorithmics · 2009
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.