The DOI matches its Crossref record; 11 of the 11 references it cites were found in a registry or an index.
Finding shortest paths on real road networks: the case for A*
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A note on two problems in connexion with graphs
Dijkstra, E. W. (1959) · Numerische Mathematik · doi:10.1007/bf01386390 · Cited by 24,043
A Formal Basis for the Heuristic Determination of Minimum Cost Paths
Hart, P., Nilsson, N., & Raphael, B. (1968) · IEEE Transactions on Systems Science and Cybernetics · doi:10.1109/tssc.1968.300136 · Cited by 12,738
Bellman, R. (1958) · Quarterly of Applied Mathematics · doi:10.1090/qam/102435 · Cited by 2,758
Problem-Solving Methods in Artificial Intelligence
Nilsson, N. J. (1971) · CERN Document Server (European Organization for Nuclear Research) · Cited by 1,607
An Appraisal of Some Shortest-Path Algorithms
Dreyfus, S. E. (1969) · Operations Research · doi:10.1287/opre.17.3.395 · Cited by 1,002
Discrete-Variable Extremum Problems
Dantzig, G. B. (1957) · Operations Research · doi:10.1287/opre.5.2.266 · Cited by 910
Shortest paths algorithms: Theory and experimental evaluation
Cherkassky, B. V., Goldberg, A. V., & Radzik, T. (1996) · Mathematical Programming · doi:10.1007/bf02592101 · Cited by 743
Shortest Path Algorithms: An Evaluation Using Real Road Networks
Zhan, F. B., & Noon, C. E. (1998) · Transportation Science · doi:10.1287/trsc.32.1.65 · Cited by 570
Heuristic shortest path algorithms for transportation applications: State of the art
Fu, L., Sun, D., & Rilett, L. R. (2006) · Computers & Operations Research · doi:10.1016/j.cor.2005.03.027 · Cited by 341
Reach-Based Routing: A New Approach to Shortest Path Algorithms Optimized for Road Networks.
Gutman, R. J. (2004) · Cited by 215
Cited by
Mapping transit‐based access: integrating GIS, routes and schedules
Lei, T. L., & Church, R. L. (2010) · International Journal of Geographical Information Science · doi:10.1080/13658810902835404 · Cited by 257
Self-citationThe Threat of Offensive AI to Organizations
Mirsky, Y., Demontis, A., Kotak, J., Shankar, R., Gelei, D., Yang, L., Zhang, X., Pintor, M., Lee, W., Elovici, Y., et al. (2023) · Computers & Security · doi:10.1016/j.cose.2022.103006 · Cited by 97
Metadata
- Authors
- Zeng, W., & Church, R. L.
- Venue
- International Journal of Geographical Information Science
- Publisher
- Informa UK Limited
- Published
- 2009-04
- Volume
- 23
- Issue
- 4
- Pages
- 531-543
- ISSN
- 0269-3798 (ISSN-L)
- 1365-8816
- 1362-3087
- OpenAlex
- W2103610940
- Cited by
- 327
- References
- 11
- FWCI
- 3.48
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Finding shortest paths on real road networks: the case for A*. https://app.cochat.ai/papers/10.1080/13658810801949850
- The paper
- Zeng, W., & Church, R. L. (2009). Finding shortest paths on real road networks: the case for A*. International Journal of Geographical Information Science. https://doi.org/10.1080/13658810801949850
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.