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

• 作者: 关佶红 张波良 张瑞昌
• 来源期刊: 计算机应用与软件
• 学科: 工学
• 关键词: 最短路径 道路网 层次化
• 年，卷（期）: 2014,（10）
• 所属期刊栏目: 综合评述
• 页码范围: 1-9
• 页数: 9页
• 分类号: TP3
• 字数: 13081字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-386x.2014.10.001

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	关佶红	同济大学计算机科学与技术系	50	522	13.0	21.0
2	张波良	复旦大学计算机科学技术学院	2	67	2.0	2.0
3	张瑞昌	复旦大学计算机科学技术学院	1	30	1.0	1.0