| 基于正六边形格网的最短路径算法 |
| |
| 引用本文： | 谢树春,尹洁,刘绍焕,王志鸿.基于正六边形格网的最短路径算法[J].测绘科学,2008,33(1):106-108. |
| |
| 作者姓名： | 谢树春 尹洁 刘绍焕 王志鸿 |
| |
| 作者单位： | 1. 中南大学信息物理工程学院,长沙,410083;长沙理工大学公路工程学院,长沙,410076
2. 长沙理工大学公路工程学院,长沙,410076 |
| |
| 摘 要： | 本文在分析了现有算法的一些不足之处的基础上,结合正六边形的特点及水流扩散思想,提出了基于正六边形格网的最短路径分析算法。该算法在最短路径搜索过程中,对同一正六边形格网而言,它至起点的累计代价值,不需要进行数据比较和修正。与经典的Dijikstra算法相比,该算法大大节约了搜索的时间。
|
| 关 键 词： | 正六边形格网 最短路径 时间复杂度 |
| 文章编号： | 1009-2307（2008）01-0106-03 |
| 收稿时间： | 2006-11-23 |
| 修稿时间： | 2006年11月23 |
The shortest path algorithm based on regular hexagon grids |
| |
| XIE Shun-chun,YIN Jie,LIU Shao-huan,WANG Zhi-hong.The shortest path algorithm based on regular hexagon grids[J].Science of Surveying and Mapping,2008,33(1):106-108. |
| |
| Authors: | XIE Shun-chun YIN Jie LIU Shao-huan WANG Zhi-hong |
| |
| Abstract: | 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. |
| |
| Keywords: | regular hexagon grids shortest path time complexity |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
