COMPARATIVE STUDY ON SINGLE SOURCE SHORTEST PATH ALGORITHM

We propose architecture for graph analysis to find out the single source shortest path to all other vertices is a common problem. The solution to this problem is Bellman - Ford's algorithm that solves such a single source shortest path (SSSP) problem and better applies to be parallelized for many core architect ures. In this we get, the high degree of parallelism is guaranteed at the cost of low work efficiency which is compared to similar algorithms in literature (e.g. Dijkstra's) involves much more redundant work and a consequent waste of power consumption. This architecture is a parallel implementation of the Bellman - Ford algorithm that explains the architectural characteristics of recent GPU architectures (i.e., NVIDIA Kepler, Maxwell) to improve performance as well as work efficiency. The architecture also pres ents different optimizations to the implementation, which are oriented both to the algorithm and to the architecture. The experiment will show that the proposed implementation provides an average speedup of 5x higher than the existing most efficient parall el implementations for SSSP, that it works on graphs where those implementations cannot work or are inefficient (e.g., graphs with negative weight edges, sparse graphs), and it reduces the redundant work caused by the parallelization process.