Eng During last 365 days Approved articles: 1911,   Articles in work: 300 Declined articles: 808 
Library
Articles and journals | Tariffs | Payments | Your profile

Back to contents

Search for the paths of the minimum total length in the graph
Galochkin Vladimir Ivanovich

PhD in Technical Science

Associate Professor, Department of Computer Science and System Programming, Volga State Technological Institute

424000, Russia, respublika Marii El, g. Ioshkar-Ola, ul. Pr. Lenina, 3

vigaloch@mail.ru

 

 

Abstract.

Author considers the problem of finding non-intersecting paths of the minimal total length from a given initial vertex to all other vertices on a weighted oriented graph k for non-negative arcs. The author shows that one can not use the "greedy" approach, that is, find the best way, remove the vertices of this path from the graph along with the incident arcs and repeat the search. The problem reduces to finding the shortest paths on an implicit graph of n ^ k vertices with some additional constraints, where n is the number of vertices of the original graph. The sparseness of the implicit graph allows us to use rational data structures, reducing the complexity of the path finder algorithm. The author executed the software implementation of the described algorithm. In the testing process, complete graphs were generated with the values of the arc weights at which the paths of the minimum total length consisted of a large number of arcs. For practical purposes and for computational possibilities, small values of k are of interest. In this case, it is correct to consider the value of k as a constant, and the complexity of the algorithm is estimated by the value O (n ^ (k + 1) log n). The necessary memory costs are O (n ^ k). The running time of the program on various tests does not contradict the obtained estimates of the complexity of the algorithm.

Keywords: Dijkstra's algorithm, Shortest path, Length of a path, Sparse graph, Implicit graph, Weighted graph, Directed graph, Graph, Yen's algorithm, Complexity of algorithms

DOI:

10.7256/2454-0714.2018.2.25124

Article was received:

29-12-2017


Review date:

03-01-2018


Publish date:

13-06-2018


This article written in Russian. You can find full text of article in Russian here .

References
1.
Dijkstra E. W. A note on two problems in connexion with graphs. // Numerische Mathematik, 1959. Vol. 1, Iss. 1. P. 269271. DOI: 10.1007/BF01386390.
2.
Kormen, T. Kh. Algoritmy: postroenie i analiz, 2-e izdanie: Per. s angl. / T. Kormen, Ch. Laizerson, R. Ristoimt, K. Shtain. M.: Izdatel'skii dom Vil'yams, 2005. 1296 s.
3.
Yen, Jin Y. Finding the k shortest loopless paths in a network. // Management Science, 1971. 17 (11). P. 712716. DOI: 10.1287/mnsc.17.11.712.
4.
Mainika E. Algoritmy optimizatsii na setyakh i grafakh: Per. s angl. / E. Mainika. M.: Mir, 1981. 323 s.
5.
Fillips D. Metody analiza setei: Per. s angl. / D. Fillips, A. Garsia-Dias. M.: Mir, 1984. 496 s.
6.
Galochkin V. I. Zadachi zaklyuchitel'nogo tura mezhdunarodnoi internet-olimpiady po informatike i programmirovaniyu 2012 goda dlya studentov Rossii i blizhaishego zarubezh'ya. // Programmnye sistemy i vychislitel'nye metody. 2012. 1. S. 17 27.