EDP Sciences logo
Subscriber Authentication Point
Search
Menu
All issues Volume 59 / No 5 (September-October 2025) RAIRO-Oper. Res., 59 5 (2025) 2419-2436 References
Open Access
Issue
RAIRO-Oper. Res.
Volume 59, Number 5, September-October 2025
Page(s) 2419 - 2436
DOI https://doi.org/10.1051/ro/2025082
Published online 05 September 2025
  • R.K. Ahuja, K. Mehlhorn, J. Orlin and R.E. Tarjan, Faster algorithms for the shortest path problem. J. ACM 37 (1990) 213–223. [Google Scholar]
  • A. Andersson and M. Thorup, A pragmatic implemention of monotone priority queues (1996). [Google Scholar]
  • G.S. Brodal, A survey on priority queues, in Space-Efficient Data Structures, Streams, and Algorithms, edited by A. Brodnik, A. López-Ortiz, V. Raman and A. Viola. Vol. 8066 of Lecture Notes in Computer Science. Springer, Heidelberg (2013) 150–163. [Google Scholar]
  • B.V. Cherkassky, A.V. Goldberg and C. Silverstein, Buckets, heaps, lists, and monotone priority queues. SIAM J. Comput. 28 (1999) 1326–1346. [Google Scholar]
  • T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, Introduction to Algorithms. MIT Press, Cambridge (2022). [Google Scholar]
  • E.V. Denardo and B.L. Fox, Shortest-route methods: 1. Reaching, pruning, and buckets. Oper. Res. 27 (1979) 161–186. [Google Scholar]
  • R. Dial, F. Glover, D. Karney and D. Klingman, A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees. Networks 9 (1979) 215–248. [Google Scholar]
  • R.B. Dial, Algorithm 360: shortest-path forest with topological ordering. Commun. ACM 12 (1969) 632–633. [Google Scholar]
  • E.W. Dijkstra, A note on two problems in connexion with graphs. Numer. Math. 1 (1959) 269–271. [Google Scholar]
  • E.A. Dinic, Economical algorithms for finding shortest paths in a network. Transp. Model. Syst. (1978) 36–44. [Google Scholar]
  • P. Emde Boas, R. Kaas and E. Zijlstra, Design and implementation of an efficient priority queue. Math. Syst. Theory 10 (1976) 99–127. [Google Scholar]
  • D. Ferone, P. Festa, A. Napoletano and T. Pastore, Shortest paths on dynamic graphs: a survey. Pesquisa Operacional 37 (2017) 487–508. [Google Scholar]
  • M.L. Fredman and R.E. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34 (1987) 596–615. [Google Scholar]
  • M.L. Fredman and D.E. Willard, Surpassing the information theoretic bound with fusion trees. J. Comput. Syst. Sci. 47 (1993) 424–436. [Google Scholar]
  • J.F. Gilsinn and C. Witzgall, A Performance Comparison of Labeling Algorithms for Calculating Shortest Path Trees. Vol. 13 of NBS Technical Note 777. National Bureau of Standards, Washington, DC (1973). [Google Scholar]
  • A.V. Goldberg, Shortest path algorithms: engineering aspects, in Algorithms and Computation, edited by P. Eades and T. Takaoka. Springer, Heidelberg (2001) 502–513. [Google Scholar]
  • A.V. Goldberg, A simple shortest path algorithm with linear average time, in Algorithms – ESA 2001, edited by G. Goos, J. Hartmanis, J. Van Leeuwen and F.M.A. Der Heide. Vol. 2161 of Lecture Notes in Computer Science. Springer, Heidelberg (2001) 230–241. [Google Scholar]
  • A.V. Goldberg, A practical shortest path algorithm with linear expected time. SIAM J. Comput. 37 (2008) 1637–1655. [Google Scholar]
  • A.V. Goldberg and C. Silverstein, Implementations of Dijkstra’s algorithm based on multi-level buckets, in Network Optimization, edited by G. Fandel, W. Trockel, P.M. Pardalos, D.W. Hearn and W.W. Hager. Vol. 450 of Lecture Notes in Economics and Mathematical Systems. Springer, Heidelberg (1997) 292–327. [Google Scholar]
  • L.E. Hitchner, A comparative investigation of the computational efficiency of shortest path algorithms. Operations Research Center, University of California, Berkeley, Report ORC (1968) 68–17. [Google Scholar]
  • E.L. Johnson, On shortest paths and sorting, in Proceedings of the ACM Annual Conference on – ACM’72. Vol. 1. ACM Press, Boston (1972) 510. [Google Scholar]
  • E.F. Moore, The Shortest Path Through a Maze. Bell Telephone System. Technical Publications, Monograph (1959). [Google Scholar]
  • C. Prins, Comparaison d’algorithmes de plus courts chemins sur des graphes routiers de grande taille. RAIRO-Oper. Res. 30 (1996) 333–357. [Google Scholar]
  • R. Raman, Priority queues: small, monotone and trans-dichotomous, in Algorithms – ESA’96, edited by G. Goos, J. Hartmanis, J. Leeuwen, J. Diaz and M. Serna. Vol. 1136 of Lecture Notes in Computer Science. Springer, Heidelberg (1996) 121–137. [Google Scholar]
  • R. Raman, Recent results on the single-source shortest paths problem. ACM SIGACT News 28 (1997) 81–87. [Google Scholar]
  • M. Thorup, On RAM priority queues, in Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. Vol. 81. SIAM (1996) 59. [Google Scholar]
  • M. Thorup, Undirected single-source shortest paths with positive integer weights in linear time. J. ACM 46 (1999) 362–394. [Google Scholar]
  • M. Thorup, Integer priority queues with decrease key in constant time and the single source shortest paths problem. J. Comput. Syst. Sci. 69 (2004) 330–353. [CrossRef] [Google Scholar]
  • M. Thorup, Equivalence between priority queues and sorting. J. ACM 54 (2007) 28. [Google Scholar]
  • P. van Emde Boas, Preserving order in a forest in less than logarithmic time and linear space. Inf. Process. Lett. 6 (1977) 80–82. [Google Scholar]
  • J. Van Leeuwen, Handbook of Theoretical Computer Science (Vol. A) Algorithms and Complexity. MIT Press, Cambridge (1991). [Google Scholar]
  • R.A. Wagner, A shortest path algorithm for edge-sparse graphs. J. ACM 23 (1976) 50–57. [Google Scholar]
  • D.E. Willard, Log-logarithmic worst-case range queries are possible in space θ(N). Inf. Process. Lett. 17 (1983) 81–84. [Google Scholar]
  • J.W.J. Williams, Algorithm 232: heapsort. Commun. ACM 7 (1964) 347–348. [CrossRef] [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.