摘要: 针对基于大规模图的最短路问题求解速度慢的问题,提出了一个基于路网等级的求最短路的快速近似算法。该算法首先求出高一层路网到起点的4个最近点和到终点的4个最近点及最短路径,由高一层路网形成的子图T再加上这8个最短路径形成图T',在T'上求起点到终点的最短路。这种设计使得该算法适合在超大规模图上求解,理论上也证明了精度可控,同时预处理数据也是可行的,从而使两点间最短路的求解速度大大提高。在纽约公路网上的测试结果说明了该算法的有效性和合理性。
滕聪. 切换到高一层路网最近四个点的最短路算法[J]. 计算机应用, 2010, 30(11): 2880-2883.
Cong Teng. Fast computation for point-to-point shortest path based on four closest nodes in higher level road network[J]. Journal of Computer Applications, 2010, 30(11): 2880-2883.