Обзор методов и алгоритмов построения кратчайших путей и перспективы их развития

Abstract

Незважаючи на численність робіт, пов’язаних з проблемою знаходження найкоротших шляхів (НШ), увага до розробки ефективних за швидкодією алгоритмів побудови НШ не зменшується. Це, в першу чергу, пояснюється тим, що в переважній більшості випадків такі алгоритми часто використовуються для вирішення окремих підзадач в багатьох додатках в різних областях природознавства і час вирішення загальної оптимізаційної задачі в значній мірі визначається часом побудови НШ. Розглядається три групи однокритеріальних алгоритмів: мережеві комбінаторні алгоритми; алгебраїчні або матричні алгоритми; алгоритми, що базуються на методах вирішення задач лінійного програмування (Linear programming, LP-methods). У статті дано огляд, аналіз та класифікацію методів і алгоритмів побудови найкоротших шляхів на мережах і графах між заданими підмножинами вузлів мережі (Single Source Shortest Path, SSSP) і між усіма парами вузлів (Shortest Path Tree, SPT або All Pairs Shortest Paths, APSP ). Наведено оцінки часової складності найкращих відомих алгоритмів для вирішення за дач SSSP і APSP комбінаторними, матричними і LP-методами для мереж з невід’ємними довжинами дуг і мереж з від’ємними довжинами дуг і циклами від’ємної довжини. Відзначається, що для вирішення окремих SSSP-задач існують «майже оптимальні» алгоритми в теорії і на практиці, в той же час для вирішення більш широкого класу задач, включаючи і APSP-проблему, є передумови для поліпшення вже існуючих алгоритмів. За останні роки еволюція методів вирішення задачі знаходження НШ була пов’язана з розробкою та подальшим удосконаленням ефективних структур абстрактних типів даних для представлення об’єктів задачі і створенням паралельних алгоритмів для багатопроцесорного розв’язання задачі. Визначено основні напрямки подальших досліджень з розробки ефективних методів і алгоритмів вирішення завдань знаходження найкоротших шляхів.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.