关键词: 最短路径, 改进, 存储结构, 方向优先+对向搜索, 搜索效率

Abstract: In the process of searching the shortest path, the traditional Dijkstra algorithm needs to traverse all vertices one by one in the network graph. The amount of calculation and storage space is large, and the search efficiency is very low. Therefore, based on the spatial characteristics of traffic network and the shortage of the traditional algorithm, storage structure is improved, and the combination of direction priority and bidirectional search is adopted. The purpose is to reduce the storage space and narrow search scope. As a result, search speed is accelerated, and search efficiency is raised. The experimental data shows that: compared with the traditional algorithm, the improved algorithm can search more effectively the shortest path in a transportation network, and has better practical value.

Key words: shortest path, improvement, storage structure, direction priority and bidirectional search, search efficiency