关键词: Arc-flags算法, 算法分析, 图划分, 最短路径, 预处理

Abstract:

The shortest path computation used in navigation system plays an important role in mobile Internet. Due to the increase of network scale and the moving terminal, the traditional serial algorithms for the calculation of the shortest path cannot meet the real-time requirements. The offline preprocessing technology is widely used in the shortest path computation. On the other hand, the increase of graph data scale will improve online query time for the shortest path query, so graph partition technology is used to partition road network graph data. The Arc-flags algorithm is a classic shortest path algorithm based on the preprocessing and graph partition technology, which provides efficient online shortest path query. Arc-flags have two main parts, one is graph partition and flags-setting algorithm and the other one is online query algorithm. Until now, existing research on Arc-flags algorithm mainly focus on the improvement of space and time-cost of preprocessing and comparison of the pros and cons of different network partitioning methods. However, the influence of the graph partitioning for Arc-flags algorithm is not analyzed in-depth. Our paper tested and analyzed the effect of different graph partitioning technology for Arc-flags algorithm in real road networks in many aspects, such as the pre-processing time, memory consumption and online query efficiency. The real road network data includes three public data sets: American New York City Road Network, American San Francisco Bay Area Road Network and American Northeast Road Network. In order to compare the effect of different graph partition technology, one graph partition tool Metis was used. We compared Arc-flags and simple Dijkstra algorithm. Arc-flags had much better performance on online query time. Also, we compared the results of Arc-flags based on different graph partition technology, the preprocessing time and the graph partition number was linear growth while the preprocessing time increased faster than the boundary point number. The graph partition number had little effect on online query time if the number arrived a large value. The searching range had little effect on online query time if the searching range reduced to a certain extent. If so, the main effect factor was memory access efficiency and so on, not the searching range. At last, we gave some reasonable graph partitioning suggestions according to our experimental results and analysis. We should use the best graph partitioning to partition road in order to reduce the boundary point number. Our research could provide some guidance to help the improve and use of the Arc-flags algorithm for shortest path algorithm in real navigation system.

Key words: Arc-flags, algorithm analysis, graph partitioning, shortest path, preprocessing