Loading [MathJax]/jax/output/SVG/config.js
Modelirovanie i Analiz Informatsionnykh Sistem
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Model. Anal. Inform. Sist.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Modelirovanie i Analiz Informatsionnykh Sistem, 2023, Volume 30, Number 1, Pages 6–15
DOI: https://doi.org/10.18255/1818-1015-2023-1-6-15
(Mi mais787)
 

This article is cited in 1 scientific paper (total in 1 paper)

Algorithms

The optimized algorithm of finding the shortest path in a multiple graph

A. V. Smirnov

P. G. Demidov Yaroslavl State University, 14 Sovetskaya str., Yaroslavl 150003, Russia
References:
Abstract: 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, polynomial algorithm.
Funding agency
This work was supported by P. G. Demidov Yaroslavl State University Project № VIP-016.
Received: 18.01.2023
Revised: 20.02.2023
Accepted: 22.02.2023
Document Type: Article
UDC: 519.17
MSC: 05C38, 05C65
Language: Russian
Citation: A. V. Smirnov, “The optimized algorithm of finding the shortest path in a multiple graph”, Model. Anal. Inform. Sist., 30:1 (2023), 6–15
Citation in format AMSBIB
\Bibitem{Smi23}
\by A.~V.~Smirnov
\paper The optimized algorithm of finding the shortest path in a multiple graph
\jour Model. Anal. Inform. Sist.
\yr 2023
\vol 30
\issue 1
\pages 6--15
\mathnet{http://mi.mathnet.ru/mais787}
\crossref{https://doi.org/10.18255/1818-1015-2023-1-6-15}
Linking options:
  • https://www.mathnet.ru/eng/mais787
  • https://www.mathnet.ru/eng/mais/v30/i1/p6
  • This publication is cited in the following 1 articles:
    1. A. V. Smirnov, “Algoritmy dlya zadach ob eilerovom tsikle i eilerovoi tsepi v kratnom grafe”, Model. i analiz inform. sistem, 30:3 (2023), 264–282  mathnet  crossref
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Моделирование и анализ информационных систем
    Statistics & downloads:
    Abstract page:51
    Full-text PDF :19
    References:20
     
      Contact us:
    math-net2025_01@mi-ras.ru
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2025