道路网上最短路径算法综述

被引：16

作者：

张波良 ^{[1
]}

张瑞昌 ^{[1
]}

关佶红 ^{[2
]}

机构：

[1] 复旦大学计算机科学技术学院

[2] 同济大学计算机科学与技术系

来源：

计算机应用与软件 | 2014年 / 31卷 / 10期

关键词：

最短路径; 道路网; 层次化;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

在道路网上计算两点之间的最短路径是图论算法的众多实际应用之一。经典的Dijkstra算法在大规模图上过于缓慢。过去十年间,这个经典问题在道路网上取得了重大突破,目前已知最快算法的运行效率比Dijkstra算法快了百万倍。这些算法都对道路网数据进行预处理,产生一定的辅助信息以加速查询,其中目标向导方法和层次化方法是两类典型方法。一些算法的实验性能良好,但缺乏理论支撑。这是因为难以用数学语言严格地刻画道路网的特性。因此,如何弥合理论与实践的差距是此问题面临的主要挑战。

引用

页码：1 / 9

页数：9