Finding Shortest Paths on Real Road Networks: The Case for A*

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 on 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). The authors 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.

• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/issn/13658816
• Supplemental Notes:
  • Abstract reprinted with permission from Taylor and Francis
• Authors:
  • Zeng, W
  • Church, R L
• Publication Date: 2009-4

Language

• English

Media Info

• Media Type: Print
• Features: References;
• Pagination: pp 531-543
• Serial:
  • International Journal of Geographical Information Science
  • Volume: 23
  • Issue Number: 4
  • Publisher: Taylor & Francis
  • ISSN: 1365-8816
  • EISSN: 1362-3087
  • Serial URL: https://www.tandfonline.com/toc/tgis20/current

Subject/Index Terms

• TRT Terms: Geographic information systems; Network analysis (Planning); Route choice; Routes and routing; Shortest path algorithms; Streets
• Uncontrolled Terms: Road networks
• Subject Areas: Highways; Planning and Forecasting; I72: Traffic and Transport Planning;

Filing Info

• Accession Number: 01138943
• Record Type: Publication
• Files: TRIS
• Created Date: Aug 31 2009 9:24AM