A Study of Different Parallel Implementations of Single Source Shortest Path Algorithms
The authors present a study of parallel implementations of Single Source Shortest Path (SSSP) algorithms. In the last three decades number of parallel SSSP algorithms have been developed and implemented on the different type of machines. They have divided some of these implementations into two groups, first are those where parallelization is achieved in the internal operations of sequential SSSP algorithm and second are where an actual graph is divided into sub-graphs, and serial SSSP algorithm executes parallel on separate processing units for each sub-graph. These parallel implementations have used PRAM, CRAY super-computer, dynamically reconfigurable processor and Graphics processing unit as platform to run them.