Design a linear time Algorithm for Finding A shortest path in Graph


Abstract in English

In this paper, we introduce an Effective algorithm to find the shortest path in Multiple – Source Graph, by choosing the path between the source and the distance that gives at least the length of the path down to the sink. This algorithm is based on the principle of iteration to access the optimal solution of the shortest-path problem, Where the algorithm steps are repeated for all the darts in the Graph. We proved that the time of implementation of the proposed algorithm in this paper is linear time O(n+L) and This is considered the best times of the algorithms at all.

References used

A. Kolokolova " Bellman-Ford algorithm" Applied Algorithms February 14, 2012
Chandy. K. M and Misra. J " Distributed Computation on Graphs: Shortest Path Algorithms" Communications of the ACM , Volume 25, Number I 1, November 1982
(Dijkstra. . W, "A note on two problems in connexion with graphs", Numer Math 1, 269–271. (1959

Download