Оптимизированный алгоритм поиска кратчайшего пути в кратном графе
https://doi.org/10.18255/1818-1015-2023-1-6-15
Аннотация
В статье рассматриваются неориентированные кратные графы произвольной натуральной кратности $k>1$. Кратный граф содержит ребра трех типов: обычные, кратные и мультиребра. Ребра последних двух типов представляют собой объединение $k$ связанных ребер, которые соединяют 2 или $(k+1)$ вершину соответственно. Связанные ребра могут использоваться только согласованно. Если вершина инцидентна кратному ребру, то она может быть инцидентна другим кратным ребрам, а также она может быть общим концом $k$ связанных ребер мультиребра. Если вершина является общим концом мультиребра, то она не может быть общим концом никакого другого мультиребра. Как и для обычного графа, для кратного графа можно ввести целочисленную функцию длины ребра и поставить задачу о кратчайшем пути между двумя вершинами. Кратный путь является объединением $k$ обычных путей, согласованных на связанных ребрах кратных и мультиребер. В статье оптимизирован полученный ранее алгоритм поиска кратчайшего пути в произвольном кратном графе. Показано, что оптимизированный алгоритм полиномиален. Таким образом, задача о кратчайшем пути является полиномиальной для любого кратного графа.
Об авторе
Александр Валерьевич Смирнов
Ярославский государственный университет им. П. Г. Демидова
Россия
Россия
Список литературы
1. A. V. Smirnov, “The Shortest Path Problem for a Multiple Graph,” Automatic Control and Computer Sciences, vol. 52, no. 7, pp. 625–633, 2018, doi: 10.3103/S0146411618070234.
2. A. V. Smirnov, “The Polynomial Algorithm of Finding the Shortest Path in a Divisible Multiple Graph,” Modeling and Analysis of Information Systems, vol. 29, no. 4, pp. 372–387, 2022, doi: 10.18255/1818-1015-2022-4-372-387.
3. E. W. Dijkstra, “A Note on Two Problems in Connexion with Graphs,” Numerische Mathematik, vol. 1, no. 1, pp. 269–271, 1959, doi: 10.1007/BF01386390.
4. H. W. Kuhn, “The Hungarian method for the assignment problem,” Naval Research Logistics Quarterly, vol. 2, no. 1-2, pp. 83–97, 1955, doi: 10.1002/nav.3800020109.
5. J. Munkres, “Algorithms for the Assignment and Transportation Problems,” Journal of the Society for Industrial and Applied Mathematics, vol. 5, no. 1, pp. 32–38, 1957, doi: 10.1137/0105003.
Рецензия
Для цитирования:
Смирнов А.В. Оптимизированный алгоритм поиска кратчайшего пути в кратном графе. Моделирование и анализ информационных систем. 2023;30(1):6-15. https://doi.org/10.18255/1818-1015-2023-1-6-15
For citation:
Smirnov A.V. The Optimized Algorithm of Finding the Shortest Path in a Multiple Graph. Modeling and Analysis of Information Systems. 2023;30(1):6-15. (In Russ.) https://doi.org/10.18255/1818-1015-2023-1-6-15
Просмотров:
335
Послать статью по эл. почте 