Re-optimizing the Performance of Shortest Path Queries Using Parallelized Combining Speedup Technique based on Bidirectional Arc flags and Multilevel Approach

摘要

Globally shortest path problems have increasing demand due to voluminous datasets in applications like roadmaps, web search engines, mobile data sets, etc., Computing shortest path between nodes in a given directed graph is a very common problem. Among the various shortest path algorithms, Dijkstra's shortest path algorithm [1] is said to have better performance with regard to run time than the other algorithms. The output of Dijkstra's shortest path algorithm can be improved with speedup techniques. In this paper a new combined speedup technique based on three speedup techniques were combined and each technique is parallelised individually and the performance of the combination is measured with respect to preprocessing time, runtime and number of nodes visited in random graphs, planar graphs and real world data sets.