A hybrid single-source shortest path algorithm


Creative Commons License

Arslan H., MANGUOĞLU M.

TURKISH JOURNAL OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCES, cilt.27, ss.2636-2647, 2019 (SCI İndekslerine Giren Dergi) identifier identifier

  • Cilt numarası: 27 Konu: 4
  • Basım Tarihi: 2019
  • Doi Numarası: 10.3906/elk-1901-23
  • Dergi Adı: TURKISH JOURNAL OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCES
  • Sayfa Sayıları: ss.2636-2647

Özet

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.