切换到高一层路网最近四个点的最短路算法  

Fast computation for point-to-point shortest path based on four closest nodes in higher level road network

作　　者：滕聪[1] 

机构地区：[1]山东经济学院统计与数学学院,济南250014

出　　处：《计算机应用》2010年第11期2880-2883,3001,共5页journal of Computer Applications

基　　金：国家自然科学基金资助项目(61070230)

摘　　要：针对基于大规模图的最短路问题求解速度慢的问题,提出了一个基于路网等级的求最短路的快速近似算法。该算法首先求出高一层路网到起点的4个最近点和到终点的4个最近点及最短路径,由高一层路网形成的子图T再加上这8个最短路径形成图T′,在T′上求起点到终点的最短路。这种设计使得该算法适合在超大规模图上求解,理论上也证明了精度可控,同时预处理数据也是可行的,从而使两点间最短路的求解速度大大提高。在纽约公路网上的测试结果说明了该算法的有效性和合理性。The point-to-point shortest path computation is one of the hot research topics today. One straight forward application is to find the optimal driving directions. To solve the difficulties in shortest path computation for large scale graph, an efficient approximation algorithm was proposed based on road network hierarchies. Four closest nodes in higher level road network to starting node and four closest nodes to ending node were computed first along with 8 corresponding shortest paths. For subgraph T which consists of only higher level roads, 8 edges corresponding to the previously computed 8 shortest paths were then added to T and results in a graph T′. In graph T′, search for the shortest path from starting node to ending node, which completed the task. This design demonstrates that the proposed algorithm is suitable to solve large scale problems. An error bound is provided for approximation shortest path. It is also possible to preprocess the data first. In real application, the computational results are quite competitive, which shows that the proposed algorithm is effective.

关 键 词：最短路问题 DIJKSTRA算法 大规模计算 路网等级 时间复杂度 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] TP18[自动化与计算机技术—计算机科学与技术]