An efficient algorithm for finding a shortest paths for all vertices in graph


Abstract in English

The all-nodes shortest paths problem is undoubtedly one of the most basic problems in algorithmic graph theory. In this paper, we introduce simple and efficient algorithm for all nodes shortest paths problem for directed (undirected) graphs. In this problem, we find the shortest path from a given source node to all other nodes in the graph, in which the shortest path is a path with minimum cost, i.e., sum of the edge weights. We proved that the complexity of the proposed algorithm in this paper depends only on the edges graph, and we show that the time of implementation of this algorithm is linear time O(m) and This is considered the best times of the algorithms at all. And a Comparison between complexity of proposed algorithm and the famous shortest path algorithms have been made, and the obtained results have shown that the complexity of the proposed algorithm is best.

References used

Allulli. L, Lichodzijewski .P and Zeh. N, "A Faster Cache- Oblivious Shortest-Path Algorithm for Undirected Graphs with Bounded Edge Lengths", www.web.cs.dal.ca
BASWANA. S AND KAVITHA. T, "FASTER ALGORITHMS FOR ALL-PAIRS APPROXIMATE SHORTEST PATHS IN UNDIRECTED GRAPHs", Jornal of ACM,52(1), pp 1- 24. 2005. www.cse.iitk.ac.in
Bernstein. A, "Near Linear Time (1 + ϵ)-Approximation for Restricted Shortest Paths in Undirected Graphs", siam, 2011
Brandes. U, "A Faster Algorithm for Betweenness Centrality", Journal of Mathematical Sociology 25(2):163-177, (2001)

Download