Searching for Shortest Path in A Large, Sparse Graph under Memory Limitation: A Successive Mixed Bidirectional Search Method
Xugang Ye, Anhua Lin, Shih-Ping Han · 2007
The problem of finding a shortest path between two nodes in a directed, positively weighted graph lies at the core of network optimization. Although it has been well studied for decades, there are always new challenges arising from a variety of applications. Among those challenges, an important one is limitation on memory, which leads to the necessity of revising the existing algorithms or designing a new one. In this paper, we propose a successive mixed bidirectional search algorithm. The key idea is to apply, in a single pass of the bidirectional search, a forward Dijkstra’s algorithm that stores the Closed list and a backward Dijkstra’s algorithm that does not store the Closed list. Besides proving the correctness of our algorithm in terms of its completeness and optimality, we also explore possible improvement. Moreover, we compare the performance of our algorithms with that of the popular divide-and-conquer technique, either as bidirectional search or as unidirectional search, in terms of theoretical properties, memory saving, and computational efficiency.