Итерационный алгоритм поиска кратчайшего пути в невзвешенном неориентированном графе
Аннотация
Существует проблема поиска наикратчайших путей между двумя вершинами в невзвешенном, неориентированном графе, которая усугубляется тем, что имеющиеся алгоритмы поиска всех путей имеют сложность не меньше O(n3). Предлагаемый же новый метод поиска кратчайшего пути в невзвешенном неориентированном графе позволяет получить все кратчайшие пути с приемлемой сложностью O(n2), а в среднем O(n). Существующий алгоритм поиск всех путей, алгоритм Флойда-Уоршелла имеет сложность O(n3), алгоритм Дейкастры, хоть и имеет сложность O(n2), однако для нахождения всех путей нужно заново пересчитывать пути для нахождении всех путей между двумя вершинами в графе. Данная статья описывает новый итерационный алгоритм, обосновывает его асимптотическую сложности и сравнивает время и результаты работ с алгоритмом Дейкасты, доказывая тем самым, что обоснование асимптотическая сложность обоснована верно, и алгоритм работает намного быстрее.
Литература
2. Planidin R.I. Programming Alorithm Routing. Vestnik studencheskoj nauki kafedry informacionnyh sistem i programmirovanija = The Bulletin of Student Science of the Department of Information Systems and Programming. 2017; (1):41-47. Available at: https://elibrary.ru/item.asp?id=32677886 (accessed 14.08.2021). (In Russ., abstract in Eng.)
3. Alam M.A., Faruq M.O. Finding Shortest Path for Road Network Using Dijkstra’s Algorithm. Bangladesh Journal of Multidisciplinary Scientific Research. 2019; 1(2):41-45. (In Eng.) DOI: https://doi.org/10.46281/bjmsr.v1i2.366
4. Erdin E., Cebe M., Akkaya K., Bulut E., Uluagac A.S. A Heuristic-Based Private Bitcoin Payment Network Formation Using Off-Chain Links. 2019 IEEE International Conference on Blockchain (Blockchain). IEEE Press, Atlanta, GA, USA; 2019. p. 294-301. (In Eng.) DOI: https://doi.org/10.1109/Blockchain.2019.00046
5. Krivoshein D.Yu., Marchenko A.M. Algorithms for dynamic all-pairs shortest path problem. Problemy razrabotki perspektivnyh mikro- i nanojelektronnyh system (MJeS) = Problems of Advanced Micro- and Nanoelectronic Systems Development (MES). 2012; (1):263-266. Available at: https://elibrary.ru/item.asp?id=17956216 (accessed 14.08.2021). (In Russ., abstract in Eng.)
6. Prihozhy A.A., Karasik O.N. Heterogenious blocked all- pairs shortest paths algorithm. Sistemnyj Analiz i Prikladnaâ Informatika = System Analysis and Applied Information Science. 2017; (3):68-75. Available at: https://elibrary.ru/item.asp?id=30731159 (accessed 14.08.2021). (In Russ., abstract in Eng.)
7. Bykova V.V. Mathematical Methods for the Analysis of Recursive Algorithms. Journal of Siberian Federal University. Mathematics & Physics. 2008; 1(3):236-246. Available at: https://www.elibrary.ru/item.asp?id=11482601 (accessed 14.08.2021). (In Russ., abstract in Eng.)
8. AbuSalim S.W.G., et al. Comparative Analysis between Dijkstra and Bellman-Ford Algorithms in Shortest Path Optimization. IOP Conference Series: Materials Science and Engineering. 2020; 917:012077. (In Eng.) DOI: https://doi.org/10.1088/1757-899X/917/1/012077
9. Yijun Z., Jiadong X., Chen L. A Fast Bi-Directional A* Algorithm Based on Quad-Tree Decomposition and Hierarchical Map. IEEE Access. 2021; 9:102877-102885. (In Eng.) DOI: https://doi.org/10.1109/ACCESS.2021.3094854
10. Sablin A.V. Formulation and analysis the problem of finding a path between two points when developing games. Proceedings of the International Conference on Information and Telecommunication Technologies and Mathematical Modeling of High-Tech Systems. RUDN University, Moscow; 2019. p. 295-298. Available at: https://elibrary.ru/item.asp?id=39207936 (accessed 14.08.2021). (In Russ., abstract in Eng.)
11. Listopad N.I., Karuk I.A., Hayder A.A. Algorithms for searching the shortest path and its modification. Informatizacija obrazovanija = Informatization of Education. 2016; (1):48-63. Available at: https://elibrary.ru/item.asp?id=32844256 (accessed 14.08.2021). (In Russ., abstract in Eng.)
12. Buynova E.L., et al. Issledovanie algoritmov poiska kratchajshih rasstojanij v setevyh modeljah [Research of algorithms for finding the shortest distances in network models]. Vestnik nauki, Ufa; 2020. p. 69-78. Available at: https://elibrary.ru/item.asp?id=42641303 (accessed 14.08.2021). (In Russ.)
13. Queiruga-Dios A., Sánchez G.R., del Rey Á.M., Demlova M. Teaching and assessing discrete mathematics. 2018 IEEE Global Engineering Education Conference (EDUCON). IEEE Press, Santa Cruz de Tenerife, Spain; 2018. p. 1568-1571. (In Eng.) DOI: https://doi.org/10.1109/EDUCON.2018.8363420
14. Knuth D. The Art of Programming. ITNOW. 2011; 53(4):18-19. (In Eng.) DOI: https://doi.org/10.1093/itnow/bwr021
15. Sao P., Lu H., Kannan R., Thakkar V., Vuduc R., Potok T. Scalable All-pairs Shortest Paths for Huge Graphs on Multi-GPU Clusters. Proceedings of the 30th International Symposium on High-Performance Parallel and Distributed Computing (HPDC '21). Association for Computing Machinery, New York, NY, USA; 2021. p. 121-131. (In Eng.) DOI: https://doi.org/10.1145/3431379.3460651
16. Qu T., Cai Z. A Fast Isomap Algorithm Based on Fibonacci Heap. In: Ed. by Y. Tan, Y. Shi, F. Buarque, A. Gelbukh, S. Das, A. Engelbrecht. Advances in Swarm and Computational Intelligence. ICSI 2015. Lecture Notes in Computer Science. 2015; 9142:225-231. Springer, Cham. (In Eng.) DOI: https://doi.org/10.1007/978-3-319-20469-7_25
17. Abuaiadh D., Kingston J.H. Are Fibonacci heaps optimal? In: Ed. by D. Z. Du, X. S. Zhang. Algorithms and Computation. ISAAC 1994. Lecture Notes in Computer Science. 1994; 834:442-450. Springer, Berlin, Heidelberg. (In Eng.) DOI: https://doi.org/10.1007/3-540-58325-4_210
18. Kozen D.C. Fibonacci Heaps. In: The Design and Analysis of Algorithms. Texts and Monographs in Computer Science. Springer, New York, NY; 1992. p. 44-47. (In Eng.) DOI: https://doi.org/10.1007/978-1-4612-4400-4_9
19. Belyaev I. Prioritetnaja ochered' na osnove binarnoj, binomial'noj i fibonnachievoj kuch i ee primenenie v mnogoagentnyh poiskovyh sistemah [Priority queue based on binary, binomial and Fibonacian heaps and its application in multi-agent search systems]. RSDN Magazine. 2012; (1):04-11. Available at: https://elibrary.ru/item.asp?id=17721928 (accessed 14.08.2021). (In Russ.)
20. Zhang W., Zhang L., Chen Y. Asynchronous Parallel Dijkstra’s Algorithm on Intel Xeon Phi Processor. In: Ed. by J. Vaidya, J. Li. Algorithms and Architectures for Parallel Processing. ICA3PP 2018. Lecture Notes in Computer Science. 2018; 11334:337-357. Springer, Cham. (In Eng.) DOI: https://doi.org/10.1007/978-3-030-05051-1_24
21. Dong X., Gu Y., Sun Y., Zhang Y. Efficient Stepping Algorithms and Implementations for Parallel Shortest Paths. Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '21). Association for Computing Machinery, New York, NY, USA; 2021. p. 184-197. (In Eng.) DOI: https://doi.org/10.1145/3409964.3461782
22. Crauser A., Mehlhorn K., Meyer U., Sanders P. A parallelization of Dijkstra's shortest path algorithm. In: Ed. by L. Brim, J. Gruska, J. Zlatuška. Mathematical Foundations of Computer Science 1998. MFCS 1998. Lecture Notes in Computer Science. 1998; 1450:722-731. Springer, Berlin, Heidelberg. (In Eng.) DOI: https://doi.org/10.1007/BFb0055823
23. Khanda A., Srinivasan S., Bhowmick S., Norris B., Das S.K. A Parallel Algorithm Template for Updating Single-Source Shortest Paths in Large-Scale Dynamic Networks. IEEE Transactions on Parallel and Distributed Systems. 2022; 33(4):929-940. (In Eng.) DOI: https://doi.org/10.1109/TPDS.2021.3084096
24. Gorbunova A.V., Chicherova A.R., Demidov A.K. Reshenie zadachi o vybore optimal'nogo marshruta s ispol'zovaniem verojatnostno-statisticheskoj modeli goroda [Solving the problem of choosing the optimal route using a probabilistic-statistical model of the city]. In: Ed. by Yu. M. Kovalev. Proceedings of the South Ural Youth School on Mathematical Modeling. Chelyabinsk, SUSU Publ.; 2016. p. 42-45. Available at: https://elibrary.ru/item.asp?id=27559513 (accessed 14.08.2021). (In Russ.)
25. Dudi T., Singhal R., Kumar R. Shortest Path Evaluation with Enhanced Linear Graph and Dijkstra Algorithm. 2020 59th Annual Conference of the Society of Instrument and Control Engineers of Japan (SICE). IEEE Press, Chiang Mai, Thailand; 2020. p. 451-456. (In Eng.) DOI: https://doi.org/10.23919/SICE48898.2020.9240227
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
