最短路径Dijkstra优化算法在GpsOne导航系统中的研究及应用

摘要

随着计算机技术、空间技术和导航定位技术的迅速发展，汽车导航系统成为综合技术应用的热门领域之一，是智能交通系统的重要组成部分，它不但能够显示电子地图及自身的位置，而且能够进行信息查询和规划到达目的地的最优路线，引导驾驶员到达目的地，从而提高道路通行率。汽车导航系统是解决现代交通问题的有效方式之一。 作为汽车导航核心部分的最短路径成为了关键问题。Dijkstra算法是目前汽车导航系统解决最短路径的理论基础，它的优点是程序设计简单、通用性强，缺点是该算法对所有的数据都作循环比较，因此在数据量大的情况下，会严重影响计算的速度。在导航系统的最短路径寻找中，需要寻找两个特定点之间的最短或近似最短路径，传统的Dijkstra算法需要把所有的点都扫描一遍，导致算法在这方面效率不高。另外，传统的Dijkstra算法采用邻接矩阵数据结构，占用空间比较多，浪费计算机的资源。因此，根据实际情况对基于Dijkstra的最短路径算法改进是有必要的。 本文对汽车导航中最短路径Dijstra算法实现进行了优化，即对路网用一个赋权有向图的“点一弧”结构来表达，不断使用直接插入排序方法对数组进行“动态地址数组排序”，缩小搜索范围，提高搜索速度：为了更好地找到符合驾驶员意愿的最短路径，把道路分为高层网络和底层网络，提出了基于道路分级的Dijkstra优化径算法。 Diikstra优化径算法是在微软的开发工具VB上编写及实现的，通过最终的运行测试，结果表明该算法能够提供高效的搜索速度和较高的精度。

目录

文摘

英文文摘

声明

第一章绪论

1.1研究背景

1.2汽车导航应用前景及发展趋势

1.3论文意义

1.4本文研究的内容

1.5论文的章节安排

第二章GpsOne定位原理与方法

2.1 GpsOne简介

2.2 GpsOne定位原理

2.3 GpsOne接收终端的组成

2.4 GpsOne模块DTGS-800介绍

第三章最短路径介绍及改进

3.1路径规划简介

3.2最短路径设计原则

3.3经典最短路径算法介绍

3.4经典最短路径的算法原理

3.5 Dijkstra算法优化途径

3.5.1优化Dijkstra算法的高效实现

3.5.2优化Dijkstra算法的基本原理

3.5.3优化Dijkstra算法实现流程图

3.6基于道路分级的最优路径算法

第四章系统平台的构建

4.1导航系统的整体构架

4.2导航系统各部分的说明

4.2.1车载终端

4.2.2应用服务中心

4.3系统整体实现

4.4应用服务中心系统的介绍

4.4.1导航路径规划

4.4.2位置查询

4.4.3报警监控

4.4.4应用服务中心所使用的开发工具

4.4.5系统主要模块与关键技术

4.5服务器程序界面与功能

第五章实验数据分析

5.1计算效率比较

5.2结果合理性比较

5.2.1三种算法结果示意图：

5.2.2导航路径合理性的对比

5.3实验数据总结

第六章结论与展望

致谢

参考文献

附录