Задача на найкоротший шлях у графі для виконавця з обмеженими ресурсами

М. С. Львов; O. I. Лемещук

doi:10.31471/1993-9965-2023-2(55)-47-53

Автор(и)

М. С. Львов Kherson State University; 27 Universytets’ka St., Kherson, Ukraine, 73003
O. I. Лемещук Kherson State University; 27 Universytets’ka St., Kherson, Ukraine, 73003

DOI:

https://doi.org/10.31471/1993-9965-2023-2(55)-47-53

Анотація

У статті висвітлено алгоритм Дейстктри, можливості його модифікації та узагальнене бачення можливостей модифікації. Особливу увагу було сконцентровано на аналізі пошуку найкоротших шляхів з обмеженими ресурсами. Дослідження проводиться з метою розширення бачення можливостей застосування алгоритмів Флойда і Дейкстри з додатковими параметрами. Водночас різні узагальнення проблеми найкоротшого шляху розглядаються рідко. Мета даної роботи – привернути увагу вчених і викладачів вищих навчальних закладів до одного із найбільш закономірних узагальнень проблеми. Пов’язані проблеми з використанням алгоритму з кількома джерелами досліджував Шимін Ван під час дослідження шляхів дорожніх мереж для зменшення часу, витраченого між зупинками, а також Пітер В. Еклунд працював над модифікацією алгоритму, який включає статичні та динамічні евристичні компоненти, та кілька вихідних вузлів. Модифікований алгоритм застосовано в тривимірній просторовій інформаційній системі (SIS) для маршрутизації транспортних засобів екстреної служби. Наше узагальнення полягає в тому, що ми розглядаємо виконавця алгоритму (wayfarer) з обмеженими ресурсами, які витрачаються на те, як ці ресурси можуть бути поповнені в деяких вершинах графа. Потрібно знайти найкоротший шлях, за яким виконавець може досягти цільової вершини, правильно витрачаючи і поповнюючи свої ресурси. Поряд з цими алгоритмами розглядаються також деякі їх окремі випадки. Наприклад, це алгоритм транзитивного замикання орієнтованого графа. Крім того, формулювання проблеми найкоротшого шляху представлено як задачу множення матриць на замкнуті півкільця. Стаття розрахована на розширення бачення застосування алгоритмів Флойда та Дейсктри з додатковими параметрами.

Завантаження

Дані завантаження ще не доступні.

Посилання

1. Dijkstra E. W. A note on two problems in connexion with graphs. Numer. Math / F. Brezzi— Springer Science +Business Media, 1959. Vol. 1, Iss. 1. P. 269–271. ISSN 0029-599X; 0945- 3245. doi:10.1007/BF01386390

Robert W. Floyd. 1962. Algorithm 97: Shortest path. Commun. ACM 5, 6 (June 1962), 345. DOI: https://doi.org/10.1145/367766.368168

Anderson J. Discrete mathematics and com- binatorics. Moscow: Williams Publishing House, 2003. URL: https://archive.org/details/ discretemathemat0000ande

Evstigneev V.A. Chapter 3: Iterative algorithms for global graph analysis. Paths and coverages. Application of graph theory in programming / Edited by A. P. Ershov. Moscow: Nauka. Main editorial office of physical and mathematical literature, 1985. P. 138–150.

Alexeev V.E., Talanov V.A. Chapter 3.4. Finding of shortest paths in a graph. Graphs. Calculation models. Data structures. Nizhny Novgorod: Nizhny Novgorod State University Publisher, 2005. P. 236-237. ISBN 5-85747-810-8. Archived on December 13, 2013 at the Wayback Machine

Cherkassky B. V., Goldberg A. V., Radzik T. Shortest paths algorithms: Theory and experimental evaluation (англ.). Math. Prog. Springer Science + Business Media, 1996. Vol. 73, Iss. 2. P. 129–174. ISSN 0025-5610; 1436-4646. doi:10.1007/BF02592101

Wang S. et al. Double-Sources Dijkstra Algorithm within Typical Urban Road Networks / Xie A., Huang X. (eds) Advances in Computer Science and Education. Advances in Intelligent and Soft Computing. 2012. Vol. 140. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642- 27945-4_24

Eklund P. W., Kirkby S., Pollitt S. A dynamic multi-source Dijkstra's algorithm for vehicle routing. 1996 Australian New Zealand Conference on Intelligent Information Systems. Proceedings. ANZIIS 96, 1996, pp. 329–333, doi: 10.1109/ANZIIS.1996.573976.