In recent times, the use of large-scale graphs involving millions of vertices are quite common in various practical applications like social networks, search engines, maps, etc., and often take up high computational resources when processing such graphs for traversal or finding shortest path between nodes. Although practical sequential implementations are possible using high-end computers and have been reported, such resources are not easily accessible. Moreover, the performance of such algorithms degrades drastically with increasing graph size. To this end, possiblity of parallelisation of graph algorithms using Graphical Processing Units (GPU) have gained significant importance, considering their high computational power and affordability, though their restrictive programming model is often difficult to get past. In this paper, we present the parallelisation of three fundamental class of graph problem - Breadth First Search, Single Source Shortest Path, and All-Pair Shortest Path, using CUDA based implementation on GPUs. We have also profiled the performance of the algorithms on a diverse set of generated and procured large graphs and have observed significant speedups as compared to the results of a sequential algorithm.
