最短路径算法加速技术及其搜索空间分析  

Shortest Path Algorithm Accelerated Technology and Search Space Analysis

作　　者：王少华[1,2] 钟耳顺[1] 张小虎[1,2] 张珣[1,2] 梁启君[1,2] 

机构地区：[1]中国科学院地理科学与资源研究所,北京100101 [2]中国科学院大学,北京100049

出　　处：《地理空间信息》2013年第6期62-65,10,共4页Geospatial Information

基　　金：国家科技支撑计划资助项目(2011BAH06B03)

摘　　要：为了分析不同最短路径算法加速技术与搜索空间的关系,首先分析了不同研究阶段最短路径算法的原理,然后在此基础上实现了不同算法,最后通过实验分析比较不同阶段算法的加速比和搜索空间的关系。结果表明,最短路径算法加速技术的加速比与搜索空间减少的倍数成线性关系,减少最短路径算法的搜索空间可大幅提升算法效率。To analyze relationship between speed-up ratio and search space of different shortest path algorithms accelerated technology,this paper analyzed the principle of diferent algorithms at irst.Then,it presented diferent implementation algorithms.At last,it compared the running time and searched space of diferent algorithms through experiments.The experiment results show that the speed-up ratio of shortest path computation is linearly related to a reduction in search space.The eiciency of the shortest path algorithm can be improved by reducing the search space.

关 键 词：最短路径算法 加速技术 搜索空间 GIS 

分 类 号：P208[天文地球—地图制图学与地理信息工程]