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.

I. Introduction

With the development of computer and information technology, the research about graph theory get a wide range of attention, and a variety of graph structures and algorithms have been proposed [2].