1. 研究目的与意义及国内外研究现状

目的:本次选题旨在将dijkstra算法改进，并设计一款地图导航软件，为人们的出行提供路线方案，给人们的出行带来方便。

研究意义:将改进后的dijkstra算法运用到实际生活和工作中，它能够降低运输成本，提高运输效率，方便人们出行，辅助交通管理等。具体可以将本次改进后的算法应用到打车软件的路径规划系统，物流运输的道路选择等。这项技术将能被广泛应用在地理信息、社会资源管理等重大领域，这将会为现代社会资源调配和交通管路起到积极的作用。

国内外研究现状

最近几年，国内的学者和专家对dijkstra算法的研究和改进非常活跃，在国内外的重要期刊上发表了许多相关的论文。例如，2005年，张渭军^[1]研究了改进的dijkstra最短路径算法及其应用。2007年，张巧荣^[2]研究了基于改进dijkstra算法的机器人路径规划方法。2008年，王战红^[3]研究了dijkstra算法的分析与改进；与此同时，余震江^[4]研究了基于最短路径dijkstra算法的铁路客运中转径路优化研究。2010年，郝新刚^[5]基于改进dijkstra算法的路径优化仿真研究。 王佳^[6]在2011年研究了基于dijkstra算法的京津冀旅游交通线路优化研究；与此同时，王峰博^[7]研究了基于dijkstra算法驾车导航路径研究与实现。 2012年，王兆南^[8]研究了基于dijkstra算法改进的海量数据最优路径计算方法研究与实现；与此同时，王树西^[9]研究了改进的dijkstra 算法在gis 路径规划中的应用。2015年，李彤^[10]研究了基于多属性优先级的动态路径规划方法。

2. 研究的基本内容

本文深入分析dijkstra算法，列举几种dijkstra算法的缺点与不足，对dijkstra算法进行改进，主要有三个方面：（1）求出最短路径的点序列，（2）多种度量值查询，例如：距离最短、时间最少、红绿灯最少、油耗最低，（3）提供多条可选路径。给出改进之后的算法、流程图、伪代码及实验算例，并对地图导航软件应用的结构设计、数据表设计、用户界面设计进行介绍。

3. 实施方案、进度安排及预期效果

实施方案：首先确定课题研究方向，然后定题，最后在导师指导下，确定设计时所需研究的问题，针对参阅相关文献，并设计应用，测试应用，验证算法可行性，最后撰写理论，完成论文。

第一阶段(2015.11.25-2016.2.22)

确定课题和研究方向，查阅相关资料，确定设计可行，撰写论文写作提纲，交给指导老师审阅。

4. 参考文献

[1]张渭军,王华. 城市道路最短路径的dijkstra算法优化[j]. 长安大学学报(自然科学版),2005,06:62-65.

[2]王战红,孙明明,姚瑶. dijkstra算法的分析与改进[j]. 湖北第二师范学院学报,2008,no.13408:12-14.