International Journal of Advanced Research in Computer and Communication Engineering

A monthly peer-reviewed online and print journal

ISSN Online 2278-1021
ISSN Print 2319-5940

Abstract: Shortest path algorithms find applications in wide domains. But to provide result for complex graphs in real time is a challenging task. So in this paper  four shortest path algorithms namely Dijkstra’s algorithm, Floyd Warshall, Bellman Ford and Jhonsons algorithm are studied and analyzed to detect parallelism in them and the parallelized version of all three is implemented using parallel computing framework OpenCL. It is found that Bellman Ford and Floyd Warshall contains fine grained parallelism while Jhonsons has less parallelism.

Keywords: Bellman-Ford, Dijkstra, Floyd Warshall.


PDF | DOI: 10.17148/IJARCCE.2018.7617