Indian Journal of Science and Technology
Year: 2016, Volume: 9, Issue: 33, Pages: 1-9
Dhirendra Pratap Singh* and Nilay Khare
Department of Computer Science and Engineering, Maulana Ajad National Institute of Technology, Bhopal - 462003, Madhya Pradesh, India; [email protected]
*Author for correspondence
Dhirendra Pratap Singh
Department of Computer Science and Engineering
The objective of this research is to propose and implement a fast parallel Single source shortest path (SSSP) algorithm on Graphics Processing Unit (GPU) based highly parallel and cost effective platform for dense and complete graphs. The proposed algorithm is a variant of Dijkstra’s algorithm for SSSP calculation for complete and dense graphs. In place of relaxing all the edges of a selected node as in Dijkstra’s algorithm, it relaxes one-one selected edge of different nodes of the graph simultaneously at any iteration. This paper shows parallel implementation of both Dijkstra’s algorithm and our modified Dijkstra’s algorithm on a GPU-based machine. We evaluate these implementations on NVIDIA Tesla C2075 GPU-based machines. Parallel implementation of proposed modified Dijkstra’s algorithm gives a two to three times speed increase over a parallel Dijkstra’s algorithm on a GPU-based machine for complete and dense graphs. The proposed algorithm has minimized the number of edges relaxed by one parallel thread at any iteration of parallel Dijkstra’s algorithm.
Keywords: CUDA, Graph Algorithm, GPU Computing, Parallel Dijkstra’s Algorithm, Parallel Single Source Shortest Path Algorithm
Subscribe now for latest articles and news.