Finding shortest paths on real road networks: the case for A*

TLDR

Shortest path identification on road networks is a core problem in network analysis, essential for navigation and spatial allocation, and efficient solutions are critical due to its frequent use. The study aims to improve state‑of‑the‑art Dijkstra implementations by exploiting GIS‑derived network properties. The authors enhance Dijkstra by incorporating GIS‑sourced data characteristics into the algorithm. Tests on real road networks show that the modified algorithm outperforms existing Dijkstra variants, offering valuable insights for GIS developers and researchers. References include Cherkassky et al.

Abstract

The problem of identifying the shortest path along a road network is a fundamental problem in network analysis, ranging from route guidance in a navigation system to solving spatial allocation problems. Since this type of problem is solved so frequently, it is important to craft an approach that is as efficient as possible. Based upon past research, it is generally accepted that several efficient implementations of the Dijkstra algorithm are the fastest at optimally solving the 'one‐to‐one' shortest path problem (Cherkassky et al. 1996 Cherkassky, B. V., Goldberg, A. V. and Radzik, T. 1996. Shortest paths algorithms: theory and experimental evaluation.. Mathematical Programming: Series A and B, 73: 129–174. [Crossref], [Web of Science ®] , [Google Scholar]). We show that the most efficient state‐of‐the‐art implementations of Dijkstra can be improved by taking advantage of network properties associated with GIS‐sourced data. The results of this paper, derived from tests of different algorithmic approaches on real road networks, will be extremely valuable for application developers and researchers in the GIS community.