| 最短路径算法:分类体系与研究进展 |
| |
| 引用本文： | 陆锋.最短路径算法:分类体系与研究进展[J].测绘学报,2001,30(3):269-275. |
| |
| 作者姓名： | 陆锋 |
| |
| 作者单位： | 中国科学院资源与环境信息系统国家重点实验室, |
| |
| 基金项目： | 国家科技攻关项目;96-B02-03-05; |
| |
| 摘 要： | 最短路径算法是计算机科学与地理信息科学等领域的研究热点。本文首先讨论了平面图的搜索策略，然后从问题类型、网络类型和实现方法3方面对最短路径算法进行了系统的分类，从理论上比较了近年来所提出的各具有较高效率的串行最短路径算法的时间复杂度，并对国内外一些相关研究进行了综合评述，结合城市交通网络的实验结果，作者对几种应用最为广泛的串行最短路径算法的运行效率进行了分析和评价，最后对最短路径算法在实时化和并行化方面的发展进行了讨论。
|
| 关 键 词： | 最短路径算法 分类 评价 计算机 地理信息系统 实时化 并行化 |
| 文章编号： | 1001-1595(2001)03-0269-07 |
Shortest Path Algorithms: Taxonomy and Advance in Research |
| |
| LU Feng.Shortest Path Algorithms: Taxonomy and Advance in Research[J].Acta Geodaetica et Cartographica Sinica,2001,30(3):269-275. |
| |
| Authors: | LU Feng |
| |
| Abstract: | The shortest path problem is a research topic in the field of geographic information science and computer science. In this paper, the author discussed the taxonomy of the shortest path algorithms from problem type, network characteristics and solution techniques, compared the time complexities of those common used sequential shortest path algorithms and evaluated the relevant researches. The most popular sequential shortest path algorithms are evaluated for their practical efficiency with urban traffic networks. The advance of time dependant and parallel shortest path algorithms is also discussed. |
| |
| Keywords: | shortest path algorithms taxonomy evaluation advance |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
