A hybrid single-source shortest path algorithm

Authors: HİLAL ARSLAN, MURAT MANGUOĞLU

Abstract: The single-source shortest path problem arises in many applications, such as roads, social applications, and computer networks. Finding the shortest path is challenging, especially for graphs that contain a large number of vertices and edges. In this work, we propose a novel hybrid method that first sparsifies a given graph by removing most edges that cannot form the shortest path tree and then applies a classical shortest path algorithm to the sparser graph. Removing all the edges that cannot form the shortest path tree would be expensive since it is equivalent to solving the original problem. Therefore, we propose an iterative bioinspired algorithm, namely the Physarum algorithm, as the first stage to sparsify the graph. We prove that the resulting sparser graph always contains the shortest path tree of the original graph. Next, a state-of-the-art algorithm such as Dijkstra's is applied to find the single-source shortest path on the resulting graph. The proposed method is therefore a two-stage hybrid algorithm and it computes the single-source shortest path exactly. We compare the accuracy and solution time of the proposed hybrid method against state-of-the-art implementation of Dijkstra's algorithm and the BFS algorithm on directed weighted and unweighted graphs, respectively, as a baseline. The results show that the proposed hybrid method achieves a significant speed improvement compared to the baseline.

Keywords: Single-source shortest path, shortest path tree, Dijkstra's algorithm, Physarum solver

Full Text: PDF