A fast algorithm for finding K shortest paths using generalized spur path reuse technique

Bi Yu Chen, Xiao Wei Chen, Hui Ping Chen, William H.K. Lam

Research output: Journal article publicationJournal articleAcademic researchpeer-review

Abstract

The problem of finding the K shortest paths (KSPs) between a pair of nodes in a road network is an important network optimization problem with broad applications. Yen's algorithm is a classical algorithm for exactly solving the KSP problem. However, it requires numerous shortest path searches, which can be computationally intensive for real large networks. This study proposes a fast algorithm by introducing a generalized spur path reuse technique. Using this technique, shortest paths calculated during the KSP finding process are stored. Accordingly, many shortest path searches can be avoided by reusing these stored paths. The results of computational experiments on several large-scale road networks show that the introduced generalized spur path reuse technique can avoid more than 98% of shortest path searches in the KSP finding process. The proposed algorithm speeds up Yen's algorithm by up to 98.7 times in experimental networks.

Original languageEnglish
Pages (from-to)516-533
Number of pages18
JournalTransactions in GIS
Volume25
Issue number1
DOIs
Publication statusPublished - Feb 2021

ASJC Scopus subject areas

  • Earth and Planetary Sciences(all)

Cite this