The purpose of the study is to improve the efficiency of Dijkstra's algorithm by using the shared memory model with OpenMP library and working on the principle of parallel execution in the implementation of the algorithm. Using Dijkstra's algorithm to find the shortest path between two nodes in a graph is quite common. However, the time complexity of the algorithm increases as the size of the graph increases, resulting in longer execution time, so parallel execution is a good option to solve the time complexity problem. In this research work, we propose a parallel computing method to improve the efficiency of Dijkstra's algorithm for large graphs.The method involves dividing the array of paths in Dijkstra's algorithm into a specified number of processors for parallel execution. We provide an implementation of the parallelized Dijkstra algorithm and access its performance using actual datasets and with different number of nodes. Our results show that Dijkstra's parallelized algorithm can significantly speed up the process compared to the sequential version of the algorithm, while reducing execution time and continuously improving CPU efficiency, making it a useful choice for finding shortest paths in large graphs.
Keywords: Dijkstra algorithm, graph, shortest paths, parallel computing, shared memory model, OpenMP library