ОГЛЯД МЕТОДІВ І АЛГОРИТМІВ ПОБУДОВИ НАЙКОРОТШИХ ШЛЯХІВ ТА ПЕРСПЕКТИВИ ЇХ РОЗВИТКУ

• Дата: 2020
• Автори: Trofymchuk, A.N., Vasyanin, V.A., Ushakova, L.P.
• Формат: Стаття
• Мова: English
• Опубліковано: V.M. Glushkov Institute of Cybernetics of NAS of Ukraine 2020
• Теми: задачі побудови найкоротших шляхів; методи і алгоритми; обчислювальна ефективність
• Онлайн доступ: https://jais.net.ua/index.php/files/article/view/484
• Назва журналу: Problems of Control and Informatics

Despite the numerous works related to the problem of finding the shortest paths (SP), attention to the development of speed-efficient algorithms for constructing SP is not reduced. 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 the SP. Three groups of singlecriterion algorithms are considered: network combinatorial algorithms; algebraic or matrix algorithms; algorithms based on methods for solving linear programming problems (LP-methods). The article provides 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 or All Pairs Shortest Paths, APSP). Estimates of the time complexity of the best known algorithms for solving SSSP 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, while at the same time, for solving a wider class of problems, including the APSP problem, there are prerequisites for improving existing algorithms. In recent years, the evolution of methods for solving the problem of finding SP has been associated with the 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.