The DOI matches its Crossref record; 38 of the 38 references it cites were found in a registry or an index.
Shortest‐path algorithms: Taxonomy and annotation
Abstract
We have evolved a classification scheme to characterize algorithms for solving shortestpath problems. The algorithms are classified according to (A) the problem type, i.e., the question being asked about the given network; (B) the input type, i.e., the salient features of the given network which impact on the design of the algorithm and selection of data structures; and (C) the type of underlying technique employed to solve the problem. An annotated bibliography of 79 selected references on shortest‐path algorithms is included. We have also provided a more complete listing of 222 references carefully culled out of a larger body of literature on shortest‐path algorithms through the year 1979.
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
Ford, D. R., & Fulkerson, D. R. (1962) · Cited by 4,072
Floyd, R. W. (1962) · Communications of the ACM · doi:10.1145/367766.368168 · Cited by 3,998
Combinatorial optimization: networks and matroids
Lawler, E. L. (2021) · Cited by 3,359
Bellman, R. (1958) · Quarterly of Applied Mathematics · doi:10.1090/qam/102435 · Cited by 2,758
Finding the K Shortest Loopless Paths in a Network
Yen, J. Y. (1971) · Management Science · doi:10.1287/mnsc.17.11.712 · Cited by 2,618
An Algorithm for Path Connections and Its Applications
Lee, C. Y. (1961) · IEEE Transactions on Electronic Computers · doi:10.1109/tec.1961.5219222 · Cited by 1,619
Efficient Algorithms for Shortest Paths in Sparse Networks
Johnson, D. B. (1977) · Journal of the ACM · doi:10.1145/321992.321993 · Cited by 1,041
An Appraisal of Some Shortest-Path Algorithms
Dreyfus, S. E. (1969) · Operations Research · doi:10.1287/opre.17.3.395 · Cited by 1,002
The shortest path through many points
Beardwood, J., Halton, J. H., & Hammersley, J. M. (1959) · Mathematical Proceedings of the Cambridge Philosophical Society · doi:10.1017/s0305004100034095 · Cited by 937
Discrete-Variable Extremum Problems
Dantzig, G. B. (1957) · Operations Research · doi:10.1287/opre.5.2.266 · Cited by 910
Ford, L. R., & Fulkerson, D. R. (1963) · Princeton University Press eBooks · doi:10.1515/9781400875184 · Cited by 891
The shortest path through a maze
Moore, E. (1959) · Medical Entomology and Zoology · Cited by 756
Suurballe, J. W. (1974) · Networks · doi:10.1002/net.3230040204 · Cited by 685
Lawler, E. L. (1972) · Management Science · doi:10.1287/mnsc.18.7.401 · Cited by 431
Optimization Algorithms for Networks and Graphs.
Coullard, C. R., Evans, J. R., & Minieka, E. (1994) · Mathematics of Computation · doi:10.2307/2153592 · Cited by 419
The shortest route through a network with time-dependent internodal transit times
Cooke, K. L., & Halsey, E. (1966) · Journal of Mathematical Analysis and Applications · doi:10.1016/0022-247x(66)90009-6 · Cited by 412
Algorithm 360: shortest-path forest with topological ordering [H]
Dial, R. B. (1969) · Communications of the ACM · doi:10.1145/363269.363610 · Cited by 369
Shortest Paths in Probabilistic Graphs
Frank, H. (1969) · Operations Research · doi:10.1287/opre.17.4.583 · Cited by 353
Yen, J. Y. (1970) · Quarterly of Applied Mathematics · doi:10.1090/qam/253822 · Cited by 346
A generalization of Dijkstra's algorithm
Knuth, D. E. (1977) · Information Processing Letters · doi:10.1016/0020-0190(77)90002-3 · Cited by 263
The shortest route problem with constraints
Joksch, H. C. (1966) · Journal of Mathematical Analysis and Applications · doi:10.1016/0022-247x(66)90020-5 · Cited by 214
Shortest-Route Methods: 1. Reaching, Pruning, and Buckets
Denardo, E. V., & Fox, B. L. (1979) · Operations Research · doi:10.1287/opre.27.1.161 · Cited by 198
Flows in Transportation Networks
(1972) · Mathematics in Science and Engineering · doi:10.1016/s0076-5392(08)x6182-x · Cited by 189
On Finding and Updating Spanning Trees and Shortest Paths
Spira, P. M., & Pan, A. (1975) · SIAM Journal on Computing · doi:10.1137/0204032 · Cited by 141
A shortest path algorithm for grid graphs
Hadlock, F. (1977) · Networks · doi:10.1002/net.3230070404 · Cited by 126
Solutions of the Shortest-Route Problem—A Review
Pollack, M., & Wiebenson, W. (1960) · Operations Research · doi:10.1287/opre.8.2.224 · Cited by 114
On finding minimum routes in a network with turn penalties
Caldwell, T. (1961) · Communications of the ACM · doi:10.1145/366105.366184 · Cited by 109
A performance comparison of labeling algorithms for calculating shortest path trees
Gilsinn, J. F. (1973) · doi:10.6028/nbs.tn.772 · Cited by 73
An algorithm for finding all shortest paths using N2.81 infinite-precision multiplications
Yuval, G. (1976) · Information Processing Letters · doi:10.1016/0020-0190(76)90085-5 · Cited by 67
Improved shortest path algorithms for transport networks
Vliet, D. V. (1978) · Transportation Research · doi:10.1016/0041-1647(78)90102-8 · Cited by 66
A Method for Finding the Shortest Route Through a Road Network
Whiting, P., & Hillier, J. A. (1960) · Journal of the Operational Research Society · doi:10.1057/jors.1960.32 · Cited by 63
On the Shortest Path Through a Number of Points
Verblunsky, S. (1951) · Proceedings of the American Mathematical Society · doi:10.1090/s0002-9939-1951-0045403-1 · Cited by 53
A lower bound on the average shortest path length in regular graphs
Cerf, V. G., Cowan, D. D., Mullin, R. C., & Stanton, R. G. (1974) · Networks · doi:10.1002/net.3230040405 · Cited by 45
Shortest path with time constraints on movement and parking
Halpern, J., & Priess, I. (1974) · Networks · doi:10.1002/net.3230040304 · Cited by 40
Shortest path algorithms for knapsack type problems
FRIEZE, A. M. (1976) · Mathematical Programming · doi:10.1007/bf01580382 · Cited by 23
The Theory of Networks and Management Science: Part II
Elmaghraby, S. E. (1970) · Management Science · doi:10.1287/mnsc.17.2.b54 · Cited by 17
Cited by
The image foresting transform: theory, algorithms, and applications
Falcao, A. X., Stolfi, J., & de Alencar Lotufo, R. (2004) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2004.1261076 · Cited by 614
A roadmap for traffic engineering in SDN-OpenFlow networks
Akyildiz, I. F., Lee, A., Wang, P., Luo, M., & Chou, W. (2014) · Computer Networks · doi:10.1016/j.comnet.2014.06.002 · Cited by 536
Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length
Orda, A., & Rom, R. (1990) · Journal of the ACM · doi:10.1145/79147.214078 · Cited by 483
An algorithm for the resource constrained shortest path problem
Beasley, J. E., & Christofides, N. (1989) · Networks · doi:10.1002/net.3230190402 · Cited by 327
An ultra-fast user-steered image segmentation paradigm: live wire on the fly
Falcao, A. X., Udupa, J. K., & Miyazawa, F. K. (2000) · IEEE Transactions on Medical Imaging · doi:10.1109/42.832960 · Cited by 275
Metadata
- Authors
- Deo, N., & Pang, C.
- Venue
- Networks
- Publisher
- Wiley
- Published
- 1984-06
- Volume
- 14
- Issue
- 2
- Pages
- 275-323
- ISSN
- 0028-3045 (ISSN-L)
- 1097-0037
- OpenAlex
- W2063317962
- Cited by
- 309
- References
- 38
- FWCI
- 4.55
- 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
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.