改进Dijkstra算法在GIS导航应用中最短路径搜索研究

摘要：

研究GIS在电子导航系统应用中的最短路径搜索效率问题.在电子导航系统中对最短路径的搜索效率要求很高.随着城市发展交通线路剧增,传统的基于Dijkstra算法的GIS导航系统不能适应日益复杂的交通线路,存在最短路径搜索效率过低的问题.考虑到GIS空间分布的特性,提出了改进的Dijkstra算法用以解决GIS导航中的最短路径搜索问题.改进算法不仅避免了传统Dijkstra算法逐个节点遍历搜索,而且根据方向优先特性缩小搜索范围,大大减少了搜索工作量,并通过改变搜索节点存储的数据结构提高了最短路径的搜索效率.实验表明,这种改进算法较之传统算法能够有效提高最短路径的搜索效率,满足了电子导航系统对最短路径搜索效率的要求,取得了满意的结果.

关键词：最短路径、搜索效率、方向优先

所属期刊栏目：39

分类号：TP301.6(计算技术、计算机技术)

资助基金：2010年湖北省高校产学研合作重点项目C2010070

在线出版日期：2013-01-05（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：245-247,257