Обзор методов и алгоритмов построения кратчайших путей и перспективы их развития
Незважаючи на численність робіт, пов’язаних з проблемою знаходження найкоротших шляхів (НШ), увага до розробки ефективних за швидкодією алгоритмів побудови НШ не зменшується. Це, в першу чергу, пояснюється тим, що в переважній більшості випадків такі алгоритми часто використовуються для вирішення ок...
Gespeichert in:
| Veröffentlicht in: | Проблемы управления и информатики |
|---|---|
| Datum: | 2020 |
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2020
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/208775 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Обзор методов и алгоритмов построения кратчайших путей и перспективы их развития / А.Н. Трофимчук, В.А. Васянин, Л.П. Ушакова // Проблемы управления и информатики. — 2020. — № 4. — С. 130-142. — Бібліогр.: 90 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-208775 |
|---|---|
| record_format |
dspace |
| spelling |
Трофимчук, А.Н. Васянин, В.А. Ушакова, Л.П. 2025-11-05T17:40:43Z 2020 Обзор методов и алгоритмов построения кратчайших путей и перспективы их развития / А.Н. Трофимчук, В.А. Васянин, Л.П. Ушакова // Проблемы управления и информатики. — 2020. — № 4. — С. 130-142. — Бібліогр.: 90 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/208775 519.168 10.1615/JAutomatInfScien.v52.i8.10 Незважаючи на численність робіт, пов’язаних з проблемою знаходження найкоротших шляхів (НШ), увага до розробки ефективних за швидкодією алгоритмів побудови НШ не зменшується. Це, в першу чергу, пояснюється тим, що в переважній більшості випадків такі алгоритми часто використовуються для вирішення окремих підзадач в багатьох додатках в різних областях природознавства і час вирішення загальної оптимізаційної задачі в значній мірі визначається часом побудови НШ. Розглядається три групи однокритеріальних алгоритмів: мережеві комбінаторні алгоритми; алгебраїчні або матричні алгоритми; алгоритми, що базуються на методах вирішення задач лінійного програмування (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. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Управление в экономических и биологических системах Обзор методов и алгоритмов построения кратчайших путей и перспективы их развития Огляд методів і алгоритмів побудови найкоротших шляхів та перспективи їх розвитку Overview of methods and algorithms of constructing shortest paths and prospects of their development Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Обзор методов и алгоритмов построения кратчайших путей и перспективы их развития |
| spellingShingle |
Обзор методов и алгоритмов построения кратчайших путей и перспективы их развития Трофимчук, А.Н. Васянин, В.А. Ушакова, Л.П. Управление в экономических и биологических системах |
| title_short |
Обзор методов и алгоритмов построения кратчайших путей и перспективы их развития |
| title_full |
Обзор методов и алгоритмов построения кратчайших путей и перспективы их развития |
| title_fullStr |
Обзор методов и алгоритмов построения кратчайших путей и перспективы их развития |
| title_full_unstemmed |
Обзор методов и алгоритмов построения кратчайших путей и перспективы их развития |
| title_sort |
обзор методов и алгоритмов построения кратчайших путей и перспективы их развития |
| author |
Трофимчук, А.Н. Васянин, В.А. Ушакова, Л.П. |
| author_facet |
Трофимчук, А.Н. Васянин, В.А. Ушакова, Л.П. |
| topic |
Управление в экономических и биологических системах |
| topic_facet |
Управление в экономических и биологических системах |
| publishDate |
2020 |
| language |
Russian |
| container_title |
Проблемы управления и информатики |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Огляд методів і алгоритмів побудови найкоротших шляхів та перспективи їх розвитку Overview of methods and algorithms of constructing shortest paths and prospects of their development |
| description |
Незважаючи на численність робіт, пов’язаних з проблемою знаходження найкоротших шляхів (НШ), увага до розробки ефективних за швидкодією алгоритмів побудови НШ не зменшується. Це, в першу чергу, пояснюється тим, що в переважній більшості випадків такі алгоритми часто використовуються для вирішення окремих підзадач в багатьох додатках в різних областях природознавства і час вирішення загальної оптимізаційної задачі в значній мірі визначається часом побудови НШ. Розглядається три групи однокритеріальних алгоритмів: мережеві комбінаторні алгоритми; алгебраїчні або матричні алгоритми; алгоритми, що базуються на методах вирішення задач лінійного програмування (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.
|
| issn |
0572-2691 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/208775 |
| citation_txt |
Обзор методов и алгоритмов построения кратчайших путей и перспективы их развития / А.Н. Трофимчук, В.А. Васянин, Л.П. Ушакова // Проблемы управления и информатики. — 2020. — № 4. — С. 130-142. — Бібліогр.: 90 назв. — рос. |
| work_keys_str_mv |
AT trofimčukan obzormetodovialgoritmovpostroeniâkratčaišihputeiiperspektivyihrazvitiâ AT vasâninva obzormetodovialgoritmovpostroeniâkratčaišihputeiiperspektivyihrazvitiâ AT ušakovalp obzormetodovialgoritmovpostroeniâkratčaišihputeiiperspektivyihrazvitiâ AT trofimčukan oglâdmetodívíalgoritmívpobudovinaikorotšihšlâhívtaperspektiviíhrozvitku AT vasâninva oglâdmetodívíalgoritmívpobudovinaikorotšihšlâhívtaperspektiviíhrozvitku AT ušakovalp oglâdmetodívíalgoritmívpobudovinaikorotšihšlâhívtaperspektiviíhrozvitku AT trofimčukan overviewofmethodsandalgorithmsofconstructingshortestpathsandprospectsoftheirdevelopment AT vasâninva overviewofmethodsandalgorithmsofconstructingshortestpathsandprospectsoftheirdevelopment AT ušakovalp overviewofmethodsandalgorithmsofconstructingshortestpathsandprospectsoftheirdevelopment |
| first_indexed |
2025-12-07T20:38:31Z |
| last_indexed |
2025-12-07T20:38:31Z |
| _version_ |
1850883348045496320 |