Parallel Bidirectional Dijkstra's Shortest Path Algorithm
Gintaras Vaira, Olga Kurasova · Frontiers in artificial intelligence and applications · 2011
This paper deals with Dijkstra's shortest path algorithm and with the possibilities of speeding-up this algorithm. This algorithm is a breadth-first-search algorithm. The search spreads circularly around the source node in order to find the shortest path from the source node to other nodes. Each following iteration is based on the results of the previous iteration, therefore parallelization of such an algorithm is complicated. The parallel Dijkstra algorithm, proposed in this paper, is based on the bidirectional Dijkstra algorithm and popular multicore technology. Such a technology enables to create a parallel algorithm based on the shared memory and most of the time for data synchronization thereby is saved. The proposed algorithm has been tested using the real road network data. The proposed parallel algorithm is almost 3 times faster than the standard Dijkstra algorithm.