Iterative Algorithm for Finding the Shortest Ways in an Unweighted Undirected Graph

Abstract

There is a problem of finding the shortest paths between two vertices in an unweighted, undirected graph, which is aggravated by the fact that the available algorithms for finding all paths have a complexity of at least . The proposed new method for finding the shortest path in an unweighted undirected graph allows obtaining all shortest paths with acceptable complexity , and on average, . The existing algorithm for finding all paths, the Floyd-Warshall algorithm has complexity , Deikastra's algorithm, although it has complexity , but to find all the paths, you need to recalculate the paths to find all the paths between two vertices in the graph. This article describes a new iterative algorithm, justifies its asymptotic complexity, and compares the time and results of work with Deikasta's algorithm, thereby proving that the justification for asymptotic complexity is justified correctly, and the algorithm works much faster.

Keywords

• search algorithm
• graph
• shortest path
• deikastra’s algorithm
• floyd-warshall algorithm