图书馆订阅: Guest
自动化与信息科学期刊

每年出版 12 

ISSN 打印: 1064-2315

ISSN 在线: 2163-9337

SJR: 0.173 SNIP: 0.588 CiteScore™:: 2

Indexed in

Overview of Methods and Algorithms for Constructing the Shortest Paths and Prospects of Their Development

卷 52, 册 8, 2020, pp. 1-13
DOI: 10.1615/JAutomatInfScien.v52.i8.10
Get accessGet access

摘要

Despite the numerous works related to the problem of finding the shortest paths (SP), attention to development of speed-efficient algorithms for constructing SP does not decrease. This is primarily due to the fact that in the overwhelming majority of cases such algorithms are often used to solve individual subtasks in many applications in various fields of natural science, and the time to solve the general optimization problem is largely determined by the time of constructing SP. Three groups of single-criterion algorithms are considered: network combinatorial algorithms; algebraic or matrix algorithms; algorithms based on methods for solving linear programming problems (LP-methods). The article presents an overview, analysis and classification of methods and algorithms for constructing the shortest paths on networks and graphs between given subsets of the network nodes (Single Source Shortest Path, SSSP) and between all pairs of nodes (Shortest Path Tree, SPT and All Pairs Shortest Paths, APSP). Estimates of the time complexity of the best known algorithms for solving SSST and APSP problems by combinatorial, matrix and LP methods for networks with non-negative arcs lengths and networks with negative arcs lengths and cycles of negative lengths are given. It is noted that for solving individual SSSP problems there are "almost optimal" algorithms in theory and practice, at the same time, for solving a wider class of problems, including APSP problem, there are prerequisites for improving existing algorithms. In recent years the evolution of methods for solving the problems of finding SP has been associated with development and further improvement of effective structures of abstract data types for representing objects of the problem and the creation of parallel algorithms for multiprocessor solving the problem. The main directions of further research on the development of effective methods and algorithms for solving the problems of finding the shortest paths are determined.

参考文献
  1. Ahuja R.K., Magnanti T.L., Orlin J.B., Network flows: theory, algorithms, and applications, Prentice-Hall, Inc. Upper Saddle River, New Jersey, 1993.

  2. Bertsekas D., Network optimization: continuous and discrete models, Athena Scientific, Belmont, 1998.

  3. Cormen T., Leiserson Ch., Rivest R., Stein C., Algorithms: construction and analysis, 2-nd edition [Russian translation], Izdatelskiy dom "Wiliyams", Moscow, 2005.

  4. Mehlhorn K., Sanders P., Algorithms and data structures. The basic toolbox, Springer, Karlsruhe; Saarbrucken, 2008, DOI: 10.1007/978-3-540-77978-0.

  5. Fakcharoenphol J., Rao S., Planar graphs, negative weight edges, shortest paths, and near linear time, Journal of Computer and System Sciences, 2006, 72, No. 5, 868-889, DOI: 10.1016/j.jcss.2005.05.007.

  6. Sanders P., Schultes D., Engineering fast route planning algorithms, In 6th Workshop on Experimental Algorithms, Lecture Notes in Computer Science, Springer, Berlin; Heidelberg, 2007, 4525, 23-36, DOI: 10.1007/978-3-540-72845-0_2.

  7. Schultes D., Route planning in road networks, PhD thesis, 2008.

  8. Madkour A., Aref W., Rehman F., Rahman M., Basalamah S., A survey of shortest-path algorithms, Cornell University, 2017, DOI: arXiv:1705.02044.

  9. Wang I-Lin., Shortest paths and multicommodity network flows: School of industrial and systems engineering Georgia Institute of technology: In Partial Fulfillment of the Requirements for the Degree Doctor of Philosophy, 2003.

  10. Johnson E., On shortest paths and sorting, In Proceedings of the ACM 25th annual conference, 1972, 1, 510-517, DOI: 10.1145/800193.569965.

  11. Fredman M., Tarjan R., Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM, 1987, 34, No. 3, 596-615, DOI: 10.1145/28869.28874.

  12. Dial R., Algorithm 360 shortest path forest with topological ordering, Communications of the ACM, 1969, 12, No. 11, 632-633, DOI: 10.1145/363269.363610.

  13. Ahuja R., Mehlhorn K., Orlin J., Tarjan R., Faster algorithms for the shortest path problem, Journal of ACM, 1990, 37, No. 2, 213-223, DOI: 10.1145/77600.77615.

  14. Thorup M., Floats, integers, and single source shortest paths, Journal of Algorithms, 2000, 35, No. 2, 189-201, DOI: 10.1006/jagm.2000.1080.

  15. Thorup M., Integer priority queues with decrease key in constant time and the single source shortest paths problem, Journal of Computer and System Sciences, 2004, 69, No. 3, 330-353. DOI: 10.1016/j.jcss.2004.04.003.

  16. Thorup M., Undirected single-source shortest paths with positive integer weights in linear time, Journal of ACM, 1999, 46, No. 3, 362-394, DOI: 10.1145/316542.316548.

  17. Pettie S., Ramachandran V., Computing shortest paths with comparisons and additions, SODA'02 Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, San Francisco, California, January 06-08, 2002, 267-276, DOI: 10.1145/545381.545417.

  18. Meyer U., Average-case complexity of single-source shortest-path algorithms: Lower and upper bounds, Journal of Algorithms, 2003, 48, No. 1, 91-134, DOI: 10.1016/S0196-6774(03)00046-4.

  19. Goldberg A.V., A simple shortest path algorithm with linear average time, In 9th European Symposium on Algorithms: of Lecture Notes in Computer Science, Springer, 2001, 2161, 230-241, DOI: 10.1007/3-540-44676-1_19.

  20. Meyer U., Sanders P., A-stepping: a parallelizable shortest path algorithm, Journal of Algorithms, 2003, 49, No. 1, 114-152, DOI: 10.1016/S0196-6774(03)00076-2.

  21. Ford Jr.L., Network flow theory, The RAND Corp., Santa Monica, California, 1956.

  22. Moore E., The shortest path through a maze, Part II. In Proceedings of the International Symposium on theory of Switching: The Annals of the Computation Laboratory of Harvard University, 1957, 285-292.

  23. Bellman R., On a routing problem, Quarterly of Applied Mathematics, 1958, 16, 87-90, DOI: 10.1090/qam/102435.

  24. Ford Jr.L., Fulkerson D., Flows in networks. Princeton, Princeton University Press, NJ, 1962.

  25. Levit B.Yu., Livshits V.N., Nonlinear network transport problems [in Russian], Transport, Moscow, 1972.

  26. Bertsekas D., A simple and fast label correcting algorithm for shortest paths, Networks, 1993, 23, No. 8, 703-709, DOI: 10.1002/net.3230230808.

  27. Goldberg A.A., Radzik T., A heuristic improvement of the Bellman-Ford algorithm, Applied Mathematics Letters, 1993, 6, No. 3, 3-6, DOI: 10.1016/0893-9659(93)90022-F.

  28. Goldfarb D., Hao J., Kai S., Shortest path algorithms using dynamic breadth-first search, Networks, 1991, 21, No. 1, 29-50, DOI: 10.1002/net.3230210105.

  29. Pallottino S., Shortest-path methods: complexity, interrelations and new propositions, Networks, 1984, 14, No. 2, 257-267, DOI: 10.1002/net.3230140206.

  30. Pape U., Implementation and efficiency of Moore algorithms for the shortest root problem, Mathematical Programming, 1974, 7, 212-222, DOI: 10.1007/BF01585517.

  31. Glover F., Glover R., Klingman D., Computational study of an improved shortest path algorithm, Networks, 1984, 14, No. 1, 25-36, DOI: 10.1002/net.3230140103.

  32. Van Emde Boas P., Kaas R., Zijlstra E., Design and implementation of an efficient priority queue, Math. Syst. Theory, 1976, 10, No. 1, 99-127, DOI: 10.1007/BF01683268.

  33. Gabow H., Tarjan R., Faster scaling algorithms for network problems, SIAM Journal on Computing, 1989, 18, No. 5, 1013-1036, DOI: 10.1137/0218069.

  34. Goldberg A., Scaling algorithms for the shortest paths problem, SIAM Journal on Computing, 1995, 24, No. 3, 494-504, DOI: 10.1137/S0097539792231179.

  35. Hung M., Divoky J., A computational study of efficient shortest path algorithms, Computers and Operations Research, 1988, 15, No. 6, 567-576.

  36. Cherkassky B., Goldberg A., Radzik T., Shortest paths algorithms: theory and experimental evaluation, Mathematical Programming, 1996, 73, No. 2, 129-174, DOI: 10.1007/BF02592101.

  37. Zhan F., Noon C., Shortest path algorithms: an evaluation using real road networks, Transportation Science, 1998, 32, No. 1, 65-73, DOI: 10.1287/trsc.32.1.65.

  38. Mehlhorn K., Naher S., The LEDA platform for combinatorial and geometric computing, Cambridge University Press, 1999, 316-359, DOI: 10.1145/204865.204889.

  39. Floyd R., Algorithm 97, shortest path, Comm. ACM, 1962, 5, No. 6, 345, DOI: 10.1145/367766.368168.

  40. Warshall S., A theorem on Boolean matrics, Journal of ACM, 1962, 9, No. 1, 11-12, DOI: 10.1145/321105.321107.

  41. Carre B., A matrix factorization method for finding optimal paths through networks, In I.E.E. Conference Publication, Computer-Aided Design, 1969, 51, 388-397.

  42. Carre B., An algebra for network routing problems, Journal of Institute of Mathematics and Its Applications, 1971, 7, 273-294.

  43. Pallottino S., Scutella M., Dual algorithms for the shortest path tree problem, Networks, 1997, 29, No. 2, 125-133, DOI: 10.1002/(SICI)1097-0037(199703)29:2<125::AID-NET7>3.0.CO;2-L.

  44. Morris J., An escalator process for the solution of linear simultaneous equations, Philos. Mag., 1946, Series 7, 37, No. 265, 106-120, DOI: 10.1080/14786444608561331.

  45. Dantzig G., All shortest routes in a graph, In Theory of Graphs (International Symposium, Rome, 1966), Gordon and Breach, New York, 1967, 91-92.

  46. Mills G., A decomposition algorithm for the shortest-route problem, Operations Research, 1966, 14, No. 2, 279-291, DOI: 10.1287/opre.14.2.279.

  47. Hu T., A decomposition algorithm for shortest paths in a network, Operations Research, 1968, 16, No. 1, 91-102, https://www.jstor.org/stable/168405.

  48. Johnson D., Efficient algorithms for shortest paths in sparse networks, Journal of the ACM, 1977, 24, No. 1, 1-13, DOI: 10.1145/321992.321993.

  49. Nakamori M., A note on the optimality of some all-shortest-path algorithms, Journal of the Operations Research Society of Japan, 1972, 15, No. 4, 201-204.

  50. Farbey B.A., Land A.H., Murchland J.D., The cascade algorithm for finding all shortest distances in a directed graph, Management Science, 1967, 14, No. 1, 19-28, https://doi.org/10.1287/mnsc.14.L19.

  51. Hu T., Revised matrix algorithms for shortest paths, SIAM Journal of Applied Mathematics, 1967, 15, No. 1, 207-218, https://www.jstor.org/stable/2946165.

  52. Land A., Stairs S., The extension of the cascade algorithm to large graphs, Management Science, 1967, 14, No. 1, 29-33, DOI: 10.1287/mnsc.14.1.29.

  53. Shimbel A., Applications of matrix algebra to communication nets, Bulletin of Mathematical Biophysics, 1951, 13, 165-178, DOI: 10.1007/BF02478225.

  54. Yang L., Chen W., An extension of the revised matrix algorithm, In IEEE International Symposium on Circuits and Systems, IEEE, (Portland, Oregon), 1989, 1996-1999, DOI: 10.1109/ISCAS. 1989.100763.

  55. Aho A., Hopcroft J., Ullman J., The design and analysis of computer algorithms, Addison-Wesley, 1974.

  56. Fredman M., New bounds on the complexity of the shortest path problems, SIAM Journal on Computing, 1976, 5, No. 1, 83-89, DOI: 10.1137/0205006.

  57. Takaoka T., A new upper bound on the complexity of the all pairs shortest path problem, Information Processing Letters, 1992, 43, No. 4, 195-199, DOI: 10.1016/0020-0190(92)90200-F.

  58. Alon N., Galil Z., Margalit O., On the exponent of the all pairs shortest path problem, Journal of Computer and System Sciences, 1997, 54, No. 2, 255-262, DOI: 10.1006/jcss.1997.1388.

  59. Takaoka T., Subcubic cost algorithms for the all pairs shortest path problem, Algorithmica, 1998, 20, No. 3, 309-318, DOI: 10.1007/PL00009198.

  60. Zwick U., All pairs shortest paths in weighted directed graphs - exact and almost exact algorithms, In Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science (Palo Alto, California), November, 1998, 310-319, DOI: 10.1109/SFCS.1998.743464.

  61. Galil Z., Margalit O., All pairs shortest paths for graphs with small integer length edges, Journal of Computer and System Sciences, 1997, 54, No. 2, 243-254, DOI: 10.1006/jcss.1997.1385.

  62. Galil Z., Margalit O., All pairs shortest distances for graphs with small integer length edges, Information and Computation, 1997, 134, 103-139.

  63. Seidel R., On the all-pairs-shortest-path problem in unweighted undirected graphs, Journal of Computer and System Sciences, 1995, 51, No. 3, 400-403, DOI: 10.1006/jcss.1995.1078.

  64. Backhouse R., Carre B., A comparison of Gaussian and Gauss-Jordan elimination in regular algebra, International Journal of Computer Mathematics, 1982, 10, No. 3-4, 311-325, DOI: 10.1080/ 00207168208803290.

  65. Goto S., Ohtsuki T., Yoshimura T., Sparse matrix techniques for the shortest path problem, IEEE Transactions on Circuits and Systems, 1976, 23, No. 12, 752-758, DOI: 10.1109/TCS. 1976.1084155.

  66. Dial R., Glover F., Karney D., Klingman D., A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees, Networks, 1979, 9, No. 3, 215-248, DOI: 10.1002/net.3230090304.

  67. Goldfarb D., Hao J., Kai S., Efficient shortest path simplex algorithms, Operations Research, 1990, 38, No. 4, 624-628, https://www.jstor.org/stable/171080.

  68. Goldfarb D., Jin Z., An O(nm)-time network simplex algorithm for the shortest path problem, Operations Research, 1999, 47, No. 3, 445-448, DOI: 10.1287/opre.47.3.445.

  69. Bertsekas D., Pallottino S., Scutella M., Polynomial auction algorithms for shortest paths, Computational Optimization and Applications, 1995, 4, No. 2, 99-125, DOI: 10.1007/BF01302891.

  70. Cerulli R., Festa P., Raiconi G., Graph collapsing in shortest path auction algorithms, Computational Optimization and Applications, 2001, 18, No. 3, 199-220, DOI: 10.1023/A:1011246118315.

  71. Papadimitriou C., Steiglitz K., Combinatorial optimization: algorithms and complexity, Prentice- Hall, Englewood Cliffs, NJ, 1982.

  72. Burton D., On the inverse shortest path problem, Department de Mathematique, Faculty des Sciences, Faculties Universities Notre-Dame de la Paix de Namur, 1993.

  73. Larsen J., Pedersen I., Experiments with the auction algorithm for the shortest path problem, Nordic Journal of Computing, 1999, 6, No. 4, 403-421.

  74. Filler M.F., One algorithm for finding the shortest paths. Discrete optimization studies [in Russian], Nauka, Moscow, 1976.

  75. Dinits E.A., Economical algorithms for finding the shortest paths in a network, Trudy Vsesoyuznogo NII sistemnykh issledovaniy, No. 4, VINITI, Moscow, 1978, 36-44.

  76. Dinits E.A., Karzanov A.V., Program for calculating the shortest paths in a network, Trudy Vsesoyuznogo NII sistemnykh issledovaniy, No. 4, VINITI, Moscow, 1978, 44-48.

  77. Karzanov A.V., Referral for the selection of the maximum element and its applications. Discrete optimization studies, Ed. by Fridman A.A., Nauka, Moscow, 1976, 340-359.

  78. Results of competition of programs for constructing the shortest distances matrix "Transport-83", Ekonomika i matematicheskie metody, Moscow, TSEMI RAN, 1985, XII, No. 3, 565-567.

  79. Cherkassky B., Georgiadis L., Goldberg A., Tarjan R., Werneck R., Shortest-path feasibility algorithms: An experimental evaluation, In ACM Journal of Experimental Algorithmics, 2009, 14, No. 2, 2.7:1.

  80. Delling D., Goldberg A., Nowatzyk A., Werneck R., PHAST: Hardware-accelerated shortest path trees, Journal of Parallel and Distributed Computing, 2013, 73, No. 7, 940-952, DOI: 10.1016/ j.jpdc.2012.02.007.

  81. Madduri K., Bader D., Berry J., Crobak J., Parallel shortest path algorithms for solving large-scale instances. In the shortest path problem: ninth DIMACS Implementation Challenge, ser. DIMACS Book, C. Demetrescu, A.V. Goldberg and D.S. Johnson, eds., American Mathematical Society, 2009, 74, 249-290, DOI: 10.1090/dimacs/074.

  82. Garey M., Johnson D., Computers and intractability: A guide to the theory of NP completeness, W.H. Freeman, San Francisco, CA, 1979.

  83. Hansen P., Bicriteria path problems. In lecture notes in economics and mathematical systems: G. Fandel & T. Gal, eds., Springer Verlag, Berlin, 1980, 177, 109-127, DOI: 10.1007/978-3-642- 48782-8_9.

  84. Warburton A., Approximation of Pareto optima in multiple-objective, shortest-path problems, Oper. Res, 1987, 35, No. 1, 70-79, DOI: 10.1287/opre.35.1.70.

  85. Ehrgott M., Gandibleux X., Multiple criteria optimization. State of the art. Annotated bibliographic surveys, Kluwer, Boston, MA, 2002, DOI: 10.1007/b101915.

  86. Vasyanin V.A., A two-criterion lexicographic algorithm for finding all shortest paths in networks, Cybernetics and Systems Analysis, 2014, 50, No. 5, 759-767, DOI: 10.1007/s10559-014-9666-9.

  87. Trofymchuk O.M., Vasyanin V.A., Simulation of packing, distribution and routing of small-size discrete flows in a multicommodity network, Journal of Automation and Information Sciences, 2015, 47, No. 7, 15-30, DOI: 10.1615/JAutomatInfScien.v47.i7.30.

  88. Vasyanin V.A., Problem of distribution and routing of transport blocks with mixed attachments and its decomposition, Journal of Automation and Information Sciences, 2015, 47, No. 2, 56-69, DOI: 10.1615/JAutomatInfScien.v47.i2.60.

  89. Kuzmenko V.N., Complexity of one packing optimization problem, Cybernetics and Systems Analysis, 2016, 52, No. 1, 76-84, DOI: 10.1007/s10559-016-9802-9.

  90. Trofymchuk O.M., Vasyanin V.A., Kuzmenko V.N., Optimization algorithms for packing of small- lot correspondence in communication networks, Cybernetics and Systems Analysis, 2016, 52, No. 2, 258-268, DOI: 10.1007/s10559-016-9822-5.

Begell Digital Portal Begell 数字图书馆 电子图书 期刊 参考文献及会议录 研究收集 订购及政策 Begell House 联系我们 Language English 中文 Русский Português German French Spain