Computing point-to-point shortest path using an approximate distance oracle
Pawan Poudel · OhioLink ETD Center (Ohio Library and Information Network) · 2008
We propose an extremely simple and efficient shortest path algorithm that computes an optimal shortest path between a pair of points in a metric space.Our algorithm works similarly to Dijkstra's algorithm, but uses heuristic information provided by an approximate distance oracle to prune nodes that cannot be on the shortest path.Our algorithm returns the exact shortest path in time (CS*) O(dim) using this linear size data structure, where S* is the number of vertices in the shortest path, dim is the doubling dimension of input graph, and C is a constant.We prove that this is nearly optimal by proving a lower-bound of (CS*) Ω(dim) .This paper presents theoretical and experimental results to prove that if there exist efficient distance oracles for road maps, then our algorithm explores very few nodes compared to Dijkstra's algorithm, A* algorithm, and Goldberg, et al's ALT algorithms.