浅谈GIS中网络分析与最短路径的实现

《浅谈GIS中网络分析与最短路径的实现》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、浅谈GIS中网络分析与最短路径的实现专业：交通信息工程及控制本科生：程海峰主导老师：林科摘要网络分析作为GIS的重要功能在电子导航、交通管理、城市规划、管线的布局设计中发挥了重要的作用。木文侧重于从网络拓扑关系的获取到最短路径算法的实现，为进一步研究GIS中网络分析的高效访问奠定基础。文章首先介绍了网络拓扑数据模型的一些基木概念，根据已有的研究经验，提出了自己有关网络数据模型中最基木的两个概念（网线和结点）的理解。在这个框架之下，又分析了网络拓扑关系的建立过程，得出了网络拓扑关系获取的一般过程。第

2、二部先介绍了最短路径算法选择的有关问题，通过查阅有关文献发现，目前解决系统最短路径问题应用最为广泛的是Dijkstra算法的思想。最后阐述了有关经典Dijkstra算法的主要思想并利用有关数据结构方面的知识写出了具体算法的实现过程。关键词：网络拓扑网络数据模型Dijkstra算法摘要I1.弓I言-1-2.网络拓扑关系的建立-2-2.1网络数据模型的基本概念-2-2.2网络拓扑关系的获取~2~3.最短路径算法-5-3.1算法选择-5-3.2传统Dijkstra算法的主要思想-5-3.3经典Dijks

3、tra算法的实现-6-参考文献-8-附录-9-1.引言随着地理信息系统产业的建立和数字化信息产品在全世界的普及，地理信息系统已经深入到各行各业。其中，网络分析是地理信息系统（GIS）最主要的功能之一。对地理网络（如交通网络）、城市基础设施网络（如各种网线、屯力网线、电话网线、供排水网线等）进行地理分析和模型化，是地理信息系统中网络分析的主要目的。近几年来面向社会的GIS应用开发不断增多，逐渐形成以MapObject和MapGuide为主流的GIS应用开发体系，但这两个系统都没有现成的网络分析功能，

4、只有通过二次开发才能实现MapObject和MapGuide的网络分析功能⑴。网络分析中最基本最关键的问题是最短路径问题。最短路径不仅仅指一般地理意义上的距离最短，述可以引申到其他的度量，如时间、费用、线路容量等。相应地，最短路径问题就成为最快路径问题、最低费用问题等。其实，无论是距离最短、时间最快述是费用最低，它们的核心算法都是最短路径算法。最短路径的求解,必须把现实生活中的道路、管线等各种网络抽象成一种数学结构,这种抽象出来的数学结构被称为网络拓扑结构。于是各种网络分析技术实现的关键在于网络拓

5、扑结构的建立和高效能最短路径算法。下面我就分别从这两方面讨论起。2.网络拓扑关系的建立网络分析是空间分析的一个重要方面，是依据网络拓扑关系（线性实体之间、线性实体与结点之间、结点与结点之间的连结、联通关系），并通过考察网络元素的空间、属性数据，对网络的性能特征进行多方面的分析计算⑵。对地理网络、城市基础设施网络进行地理分析和模型化的关键技术是用什么样的方式抽象出网络拓扑结构，及节点与节点的连通关系，并对网络拓扑结构进行高效能访问。2.1网络数据模型的基本概念网络是由若干线性实体互连而成的一个系统，

6、资源由网络来传输，实体间的联络也由网络来达成。网络数据模型是真实世界中网络系统（如交通网、通讯网、自来水网等）的抽象表示。构成网络的基本元素是上述线性实体以及这些实体的连结交汇点⑶。前者被称为网线或链（link）,后者一般称为结点（node）。网线构成网络的骨架，是资源传输或通讯网络的通道，可以代表公路、铁路、航线、水管、河流等；结点是网线的端点,又是网线的交汇点，可以表示交叉路口、中转站、河流汇合点等。除了上述基木网络元素之外，网络还可能有若干附属元素，如在路径分析中用来表示途径地点的站点；在资

7、源分配中用来表示资源发散地点或资源汇聚地点的中心；对资源传输或通讯网络起阻断作用的障碍等。针对网络分析的需要，作为网络基木元素的网线或结点除自身的常规属性外，还要具有一些特殊属性的数据。比如，为了实施路径分析和资源分配，网线数据应包含正反两个方面上的阻碍度以及资源需求量，而节点数据也应该包含资源需求量。2.2网络拓扑关系的获取GIS中的数据（如道路、管网、水系等）要进行最短路径的计算,就必须首先将其按结点和边的关系抽彖为图的结构，这在GIS中称为构建网络的拓扑关系。只有建立了拓扑关系，我们才能进行

8、网络路径分析。在GIS系统拓扑数据结构中，通常具有如下三种重要的拓扑形式：说明线吊如何相连的连通性，即线吊是在结点上相互连接的。多边形是由一系列相连通的线串组成的。记录多边形的相邻信息已表示拓扑结构的连续性是根据线吊的走向，可以决定谁是左多边形。同时，量多变形之所以相邻是因为二者具有共同的边界。为了能够更好的描述路网拓扑结构的建立过程，首先介绍一下描述路网的基本要素及各要素的展性。描述路网的基本要素：点对象：路网中道路和道路的交叉点以及道路的端点。先对象：用弧或链表示路段，形成路段