Research on improved bidirectional Dijkstra shortest path based on heap structures
Hongzhuan Zhao, Jianyu Mao, Luchen Wang, Ruijue Tian, Tao Wang, Dan Zhou, Y.X. Zhang, Changhe Nong, Qiuyu Liu, Chuling Zhao · 2025
With the development of the automotive industry, urban transportation systems face increasingly complex challenges. To address the slow computation and low efficiency of the traditional Dijkstra's algorithm in large-scale road networks, this study proposes the following improvements: firstly, it employs binary, 4-ary, and pairing heap structures to accelerate shortest path calculations; secondly, it introduces a bidirectional strategy to reduce unnecessary node traversals; finally, real-world road network data for Guilin and Nanning obtained via OpenStreetMap (OSM) are used to compare computation times of unidirectional and bidirectional Dijkstra algorithms under different heap structures. The results demonstrate that the bidirectional search strategy significantly enhances efficiency in large-scale networks, while the binary heap structure provides optimal performance in scenarios involving frequent updates and traversals, effectively reducing computation time. This research provides efficient algorithmic support for urban traffic path planning and lays theoretical and data foundations for further study of multi-heap structures in shortest path problems.