Geodesic
The optimized algorithm of finding the shortest path in a multiple graph
Modelirovanie i analiz informacionnyh sistem, Tome 30 (2023) no. 1, pp. 6-15 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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.
Keywords: multiple graph, multiple path, shortest path, reachability set
Mots-clés : polynomial algorithm. 
@article{MAIS_2023_30_1_a0,
     author = {A. V. Smirnov},
     title = {The optimized algorithm of finding the shortest path in a multiple graph},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {6--15},
     year = {2023},
     volume = {30},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2023_30_1_a0/}
}
TY  - JOUR
AU  - A. V. Smirnov
TI  - The optimized algorithm of finding the shortest path in a multiple graph
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2023
SP  - 6
EP  - 15
VL  - 30
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/MAIS_2023_30_1_a0/
LA  - ru
ID  - MAIS_2023_30_1_a0
ER  - 
%0 Journal Article
%A A. V. Smirnov
%T The optimized algorithm of finding the shortest path in a multiple graph
%J Modelirovanie i analiz informacionnyh sistem
%D 2023
%P 6-15
%V 30
%N 1
%U http://geodesic.mathdoc.fr/item/MAIS_2023_30_1_a0/
%G ru
%F MAIS_2023_30_1_a0
A. V. Smirnov. The optimized algorithm of finding the shortest path in a multiple graph. Modelirovanie i analiz informacionnyh sistem, Tome 30 (2023) no. 1, pp. 6-15. http://geodesic.mathdoc.fr/item/MAIS_2023_30_1_a0/

[1] A. V. Smirnov, “The Shortest Path Problem for a Multiple Graph”, Automatic Control and Computer Sciences, 52:7 (2018), 625–633 | DOI | MR

[2] A. V. Smirnov, “The Polynomial Algorithm of Finding the Shortest Path in a Divisible Multiple Graph”, Modeling and Analysis of Information Systems, 29:4 (2022), 372–387 | DOI | MR

[3] E. W. Dijkstra, “A Note on Two Problems in Connexion with Graphs”, Numerische Mathematik, 1:1 (1959), 269–271 | DOI | MR | Zbl

[4] H. W. Kuhn, “The Hungarian method for the assignment problem”, Naval Research Logistics Quarterly, 2:1-2 (1955), 83–97 | DOI | MR | Zbl

[5] J. Munkres, “Algorithms for the Assignment and Transportation Problems”, Journal of the Society for Industrial and Applied Mathematics, 5:1 (1957), 32–38 | DOI | MR