摘要
本文在分析了现有算法的一些不足之处的基础上,结合正六边形的特点及水流扩散思想,提出了基于正六边形格网的最短路径分析算法。该算法在最短路径搜索过程中,对同一正六边形格网而言,它至起点的累计代价值,不需要进行数据比较和修正。与经典的Dijikstra算法相比,该算法大大节约了搜索的时间。
In this paper, the authors analyze the insufficiency of existed algorithms, combine the geometrical character of the regular hexagon grid with the idea of water diffusion, and propose a new shortest path algorithm based on the regular hexagon grids data.During the search process of new algorithm, the accumulation cost that account from any regular hexagon grid to starting search grid should not be modified.As a result, compared with the classic algorithm of Dijikstra, the time complexity of new algorithm is O(nn),which save the searching time significantly.
出处
《测绘科学》
CSCD
北大核心
2008年第1期106-108,共3页
Science of Surveying and Mapping
