|Articles and journals | Tariffs | Payments | Your profile|
Search for the paths of the minimum total length in the graph
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
Article was received:29-12-2017
This article written in Russian. You can find full text of article in Russian here .