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

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

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 i...

Повний опис

Збережено в:
Бібліографічні деталі
Дата: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

Репозитарії

Problems of Control and Informatics
id oai:ojs2.jais.net.ua:article-484
record_format ojs
institution Problems of Control and Informatics
baseUrl_str
datestamp_date 2025-03-14T15:38:44Z
collection OJS
language English
topic задачі побудови найкоротших шляхів
методи і алгоритми
обчислювальна ефективність
spellingShingle задачі побудови найкоротших шляхів
методи і алгоритми
обчислювальна ефективність
Trofymchuk, A.N.
Vasyanin, V.A.
Ushakova, L.P.
ОГЛЯД МЕТОДІВ І АЛГОРИТМІВ ПОБУДОВИ НАЙКОРОТШИХ ШЛЯХІВ ТА ПЕРСПЕКТИВИ ЇХ РОЗВИТКУ
topic_facet задачі побудови найкоротших шляхів
методи і алгоритми
обчислювальна ефективність
shortest path problems
methods and algorithms
computational efficiency
format Article
author Trofymchuk, A.N.
Vasyanin, V.A.
Ushakova, L.P.
author_facet Trofymchuk, A.N.
Vasyanin, V.A.
Ushakova, L.P.
author_sort Trofymchuk, A.N.
title ОГЛЯД МЕТОДІВ І АЛГОРИТМІВ ПОБУДОВИ НАЙКОРОТШИХ ШЛЯХІВ ТА ПЕРСПЕКТИВИ ЇХ РОЗВИТКУ
title_short ОГЛЯД МЕТОДІВ І АЛГОРИТМІВ ПОБУДОВИ НАЙКОРОТШИХ ШЛЯХІВ ТА ПЕРСПЕКТИВИ ЇХ РОЗВИТКУ
title_full ОГЛЯД МЕТОДІВ І АЛГОРИТМІВ ПОБУДОВИ НАЙКОРОТШИХ ШЛЯХІВ ТА ПЕРСПЕКТИВИ ЇХ РОЗВИТКУ
title_fullStr ОГЛЯД МЕТОДІВ І АЛГОРИТМІВ ПОБУДОВИ НАЙКОРОТШИХ ШЛЯХІВ ТА ПЕРСПЕКТИВИ ЇХ РОЗВИТКУ
title_full_unstemmed ОГЛЯД МЕТОДІВ І АЛГОРИТМІВ ПОБУДОВИ НАЙКОРОТШИХ ШЛЯХІВ ТА ПЕРСПЕКТИВИ ЇХ РОЗВИТКУ
title_sort огляд методів і алгоритмів побудови найкоротших шляхів та перспективи їх розвитку
title_alt OVERVIEW OF METHODS AND ALGORITHMS OF CONSTRUCTING SHORTEST PATHS AND PROSPECTS OF THEIR DEVELOPMENT
description 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.
publisher V.M. Glushkov Institute of Cybernetics of NAS of Ukraine
publishDate 2020
url https://jais.net.ua/index.php/files/article/view/484
work_keys_str_mv AT trofymchukan overviewofmethodsandalgorithmsofconstructingshortestpathsandprospectsoftheirdevelopment
AT vasyaninva overviewofmethodsandalgorithmsofconstructingshortestpathsandprospectsoftheirdevelopment
AT ushakovalp overviewofmethodsandalgorithmsofconstructingshortestpathsandprospectsoftheirdevelopment
AT trofymchukan oglâdmetodívíalgoritmívpobudovinajkorotšihšlâhívtaperspektiviíhrozvitku
AT vasyaninva oglâdmetodívíalgoritmívpobudovinajkorotšihšlâhívtaperspektiviíhrozvitku
AT ushakovalp oglâdmetodívíalgoritmívpobudovinajkorotšihšlâhívtaperspektiviíhrozvitku
first_indexed 2025-10-30T02:49:15Z
last_indexed 2025-10-30T02:49:15Z
_version_ 1847373391140487168
spelling oai:ojs2.jais.net.ua:article-4842025-03-14T15:38:44Z OVERVIEW OF METHODS AND ALGORITHMS OF CONSTRUCTING SHORTEST PATHS AND PROSPECTS OF THEIR DEVELOPMENT ОГЛЯД МЕТОДІВ І АЛГОРИТМІВ ПОБУДОВИ НАЙКОРОТШИХ ШЛЯХІВ ТА ПЕРСПЕКТИВИ ЇХ РОЗВИТКУ Trofymchuk, A.N. Vasyanin, V.A. Ushakova, L.P. задачі побудови найкоротших шляхів методи і алгоритми обчислювальна ефективність shortest path problems methods and algorithms computational efficiency 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. Незважаючи на численність робіт, пов’язаних з проблемою знаходження найкоротших шляхів (НШ), увага до розробки ефективних за швидкодією алгоритмів побудови НШ не зменшується. Це, в першу чергу, пояснюється тим, що в переважній більшості випадків такі алгоритми часто використовуються для вирішення окремих підзадач в багатьох додатках в різних областях природознавства і час вирішення загальної оптимізаційної задачі в значній мірі визначається часом побудови НШ. Розглядається три групи однокритеріальних алгоритмів: мережеві комбінаторні алгоритми; алгебраїчні або матричні алгоритми; алгоритми, що базуються на методах вирішення задач лінійного програмування (Linear programming, LP-methods). У статті дано огляд, аналіз та класифікацію методів і алгоритмів побудови найкоротших шляхів на мережах і графах між заданими підмножинами вузлів мережі (Single Source Shortest Path, SSSP) і між усіма парами вузлів (Shortest Path Tree, SPT або All Pairs Shortest Paths, APSP ). Наведено оцінки часової складності найкращих відомих алгоритмів для вирішення задач SSSP і APSP комбінаторними, матричними і LP-методами для мереж з невід’ємними довжинами дуг і мереж з від’ємними довжинами дуг і циклами від’ємної довжини. Відзначається, що для вирішення окремих SSSP-задач існують «майже оптимальні» алгоритми в теорії і на практиці, в той же час для вирішення більш широкого класу задач, включаючи і APSP-проблему, є передумови для поліпшення вже існуючих алгоритмів. За останні роки еволюція методів вирішення задачі знаходження НШ була пов’язана з розробкою та подальшим удосконаленням ефективних структур абстрактних типів даних для представлення об’єктів задачі і створенням паралельних алгоритмів для багатопроцесорного розв’язання задачі. Визначено основні напрямки подальших досліджень з розробки ефективних методів і алгоритмів вирішення завдань знаходження найкоротших шляхів. V.M. Glushkov Institute of Cybernetics of NAS of Ukraine 2020-08-20 Article Article application/pdf https://jais.net.ua/index.php/files/article/view/484 10.1615/JAutomatInfScien.v52.i8.10 Міжнародний науково-технічний журнал "Проблеми керування та інформатики"; Том 65 № 4 (2020): Міжнародний науково-технічний журнал "Проблеми керування та інформатики"; 130-142 International Scientific Technical Journal "Problems of Control and Informatics; Том 65 № 4 (2020): International Scientific Technical Journal "PROBLEMS OF CONTROL AND INFORMATICS"; 130-142 International Scientific Technical Journal "Problems of Control and Informatics"; Vol. 65 No. 4 (2020): International Scientific Technical Journal "PROBLEMS OF CONTROL AND INFORMATICS"; 130-142 2786-6505 2786-6491 en https://jais.net.ua/index.php/files/article/view/484/554 Copyright (c) 2020 A.N. Trofymchuk, V.A. Vasyanin, L.P. Ushakova https://creativecommons.org/licenses/by-nc-nd/4.0

Схожі ресурси