Dijkstra´s shortest path algorithm serial and parallel execution performance analysis

This article introduces the problem of parallelization of Dijkstra´s algorithm, a well known algorithm for computing single-source shortest path in a graph. Dijkstra´s algorithm can be applied to graphs with a various number of vertices and edges. Dijkstra´s shortest path algorithm is implemented and presented, and the performances of its parallel and serial execution are compared. The algorithm implementation was parallelized using OpenMP (Open Multi-Processing) and OpenCL (Open Computing Language) standards. Its performances were measured on 4 different configurations, based on dual core and i5 processors. The experimental results prove that the parallel execution of the algorithm has good performances in terms of speed-up ratio, when compared to its serial execution. Finally, the results show that, because of Dijkstra´s algorithm in itself is sequential, and difficult to parallelize, average speed-up ratio achieved by parallelization is only 10%. This proves to be a huge disadvantage of this algorithm, because its use is widespread, and enhancing its performance would have great effects in its many uses.