maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2023-1-6-15mais-1763Research ArticleAlgorithmsОптимизированный алгоритм поиска кратчайшего пути в кратном графеThe Optimized Algorithm of Finding the Shortest Path in a Multiple Graphhttps://orcid.org/0000-0002-0980-2507СмирновАлександр ВалерьевичSmirnovAlexander Valeryevichalexander_sm@mail.ruЯрославский государственный университет им. П. Г. ДемидоваРоссияP. G. Demidov Yaroslavl State UniversityRussian Federation202328042023301615Copyright © Смирнов А.В., 20232023Смирнов А.В.Smirnov A.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/1763

В статье рассматриваются неориентированные кратные графы произвольной натуральной кратности $k>1$. Кратный граф содержит ребра трех типов: обычные, кратные и мультиребра. Ребра последних двух типов представляют собой объединение $k$ связанных ребер, которые соединяют 2 или $(k+1)$ вершину соответственно. Связанные ребра могут использоваться только согласованно. Если вершина инцидентна кратному ребру, то она может быть инцидентна другим кратным ребрам, а также она может быть общим концом $k$ связанных ребер мультиребра. Если вершина является общим концом мультиребра, то она не может быть общим концом никакого другого мультиребра. Как и для обычного графа, для кратного графа можно ввести целочисленную функцию длины ребра и поставить задачу о кратчайшем пути между двумя вершинами. Кратный путь является объединением $k$ обычных путей, согласованных на связанных ребрах кратных и мультиребер. В статье оптимизирован полученный ранее алгоритм поиска кратчайшего пути в произвольном кратном графе. Показано, что оптимизированный алгоритм полиномиален. Таким образом, задача о кратчайшем пути является полиномиальной для любого кратного графа.

In this paper, we study undirected multiple graphs of any natural multiplicity $k>1$. There are edges of three types: ordinary edges, multiple edges and multi-edges. Each edge of the last two types is a union of $k$ linked edges, which connect 2 or $(k+1)$ vertices, correspondingly. The linked edges should be used simultaneously. If a vertex is incident to a multiple edge, it can be also incident to other multiple edges and it can be the common end of $k$ linked edges of some multi-edge. If a vertex is the common end of some multi-edge, it cannot be the common end of another multi-edge. As for an ordinary graph, we can define the integer function of the length of an edge for a multiple graph and set the problem of the shortest path joining two vertices. Any multiple path is a union of $k$ ordinary paths, which are adjusted on the linked edges of all multiple and multi-edges. In the article, we optimize the algorithm of finding the shortest path in an arbitrary multiple graph, which was obtained earlier. We show that the optimized algorithm is polynomial. Thus, the problem of the shortest path is polynomial for any multiple graph.

кратный графкратный путькратчайший путьмножество достижимостиполиномиальный алгоритмmultiple graphmultiple pathshortest pathreachability setpolynomial algorithmРабота выполнена в рамках инициативной НИР ЯрГУ им. П. Г. Демидова No VIP-016.This work was supported by P. G. Demidov Yaroslavl State University Project No VIP-016.ReferencesA. 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.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.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.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.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.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.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.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.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.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.

The authors declare that there are no conflicts of interest present.