%0 Journal Article
%T 切换到高一层路网最近四个点的最短路算法
%A 滕聪
%J 计算机应用
%D 2010
%X ？针对基于大规模图的最短路问题求解速度慢的问题,提出了一个基于路网等级的求最短路的快速近似算法。该算法首先求出高一层路网到起点的4个最近点和到终点的4个最近点及最短路径,由高一层路网形成的子图t再加上这8个最短路径形成图t',在t'上求起点到终点的最短路。这种设计使得该算法适合在超大规模图上求解,理论上也证明了精度可控,同时预处理数据也是可行的,从而使两点间最短路的求解速度大大提高。在纽约公路网上的测试结果说明了该算法的有效性和合理性。
%K 最短路问题
%K dijkstra算法
%K 大规模计算
%K 路网等级
%K 时间复杂度
%U http://www.joca.cn/CN/abstract/abstract13375.shtml