engleski

Goal Directed Shortest Path Queries Using Precomputed Cluster Distances

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.

shortest paths

nije evidentirano