基于导航数据最短路径算法的实现及在GIS中的应用

摘要

近年来，随着地理信息系统（GeographicInformationSystem，简称GIS）和导航技术的快速发展，二者的结合在社会的各行各业中得到了广泛的应用。最短路径计算作为二者理论和应用中最基本、最关键的技术，它既是计算机科学和地理信息科学领域的一个研究热点，也是GIS和导航应用中的一个重点。广泛应用于交通、旅游、城市规划、物流、电力电子导航等多个领域。
　　最短路径计算作为GIS网络分析功能和导航功能的计算理论基础，在实际应用中，并非纯理论上的最短路径计算，而是以具体的导航数据为出发点，考虑各种实际限制条件进行计算的。本文正是基于这一点，详细地论述了基于实际导航数据的最短路径算法的实现与优化的方法。具体包括四个方面的内容:
　　(1)详细分析了课题使用的导航数据的格式，在此基础上对课题使用到的数据结构进行提炼和组织。
　　(2)对导航数据进行预处理，主要包括整理、优化、归类和排序等，最终形成课题需要的数据。
　　(3)结合本课题导航数据数的特点，设计了“尾点判断”算法，实现了课题中的禁止规则的计算。
　　(4)采用以节点为基准，建立了节点数据、路段数据及禁止数据三者之间的排序拓扑结构，采用对所有已标识节点到所有未标识节点的距离进行按升序排序的方法提高Dijkstra算法的速度和效率。并以此为基础，实现了在禁止规则限制条件下以Dijkstra算法为基础的地图上任意两点间的最短路径的计算。

目录

声明

摘要

1 绪论

1．1 课题背景及意义

1．2 国内外研究现状及应用

1．2．1 最短路径算法的研究现状

1．2．2 最短路径算法应用于GIS和导航的研究现状

1．2．3 最短路径在GIS和导航中的应用

1．3 论文的主要内容

1．4 论文结构

2 背景知识概述

2．1 GIS与导航

2．1．1 GIS概述

2．1．2 导航概述

2．2 最短路径算法

2．2．1 最短路径算法的概念

2．2．2 常用最短路径算法

2．2．3 最短路径算法比较

3 导航数据结构分析及处理

3．1 导航数据格式

3．1．1 导航数据格式的分类

3．1．2 主流导航数据格式

3．2 导航数据预处理

3．2．1 数据预处理

3．2．2 导航数据要素属性定义

3．2．3 导航数据预处理

3．2．4 预处理数据的实例展示

4 最短路径算法优化与实现及在GIS中的应用

4．1 最短路径算法及优化

4．1．1 禁止规则算法

4．1．2 Dijkstra算法的优化

4．1．3 Dijkstra优化前后的实验结果比较

4．2 最短路径算法的数据结构

4．2．1 经典Dijkstra算法的数据结构

4．2．2 Dijkstra优化算法的数据结构

4．3 最短路径算法实现

4．3．1 利用尾点判断法进行禁止规则计算的实现

4．3．2 Dijkstra优化算法实现

4．4 最短路径优化算法在GIS中的应用

4．4．1 GIS实际应用中两点间最短路径的计算

4．4．2 GIS应用实例展示

5 总结与展望

致谢

参考文献