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

浅谈GIS中网络分析与最短路径的实现 专业：交通信息工程及控制 本科生：程海峰 主导老师：林科 摘 要 网络分析作为GIS的重要功能在电子导航、交通管理、城市规划、管线的布局设计中发挥了重要的作用。本文侧重于从网络拓扑关系的获取到最短路径算法的实现，为进一步研究GIS中网络分析的高效访问奠定基础。 文章首先介绍了网络拓扑数据模型的一些基本概念，根据已有的研究经验，提出了自己有关网络数据模型中最基本的两个概念（网线和结点）的理解。在这个框架之下，又分析了网络拓扑关系的建立过程，得出了网络拓扑关系获取的一般过程。第二部先介绍了最短路径算法选择的有关问题，通过查阅有关文献发现，目前解决系统最短路径问题应用最为广泛的是Dijkstra算法的思想。最后阐述了有关经典Dijkstra算法的主要思想并利用有关数据结构方面的知识写出了具体算法的实现过程。 关键词：网络拓扑 网络数据模型 Dijkstra算法 目 录 摘 要 I 1. 引 言 - 1 - 2. 网络拓扑关系的建立 - 2 - 2.1 网络数据模型的基本概念 - 2 - 2.2 网络拓扑关系的获取 - 2 - 3. 最短路径算法 - 5 - 3.1 算法选择 - 5 - 3.2 传统Dijkstra算法的主要思想 - 5 - 3.3 经典Dijkstra算法的实现 - 6 - 参考文献 - 8 - 附 录 - 9 - 1. 引 言 随着地理信息系统产业的建立和数字化信息产品在全世界的普及，地理信息系统已经深入到各行各业。其中，网络分析是地理信息系统（GIS）最主要的功能之一。对地理网络（如交通网络）、城市基础设施网络（如各种网线、电力网线、电话网线、供排水网线等）进行地理分析和模型化，是地理信息系统中网络分析的主要目的。近几年来面向社会的GIS应用开发不断增多,逐渐形成以MapObject和MapGuide为主流的GIS应用开发体系，但这两个系统都没有现成的网络分析功能,只有通过二次开发才能实现MapObject和MapGuide的网络分析功能。? ?网络分析中最基本最关键的问题是最短路径问题。最短路径不仅仅指一般地理意义上的距离最短,还可以引申到其他的度量,如时间、费用、线路容量等。相应地,最短路径问题就成为最快路径问题、最低费用问题等。其实,无论是距离最短、时间最快还是费用最低,它们的核心算法都是最短路径算法。? 最短路径的求解,必须把现实生活中的道路、管线等各种网络抽象成一种数学结构,这种抽象出来的数学结构被称为网络拓扑结构。于是各种网络分析技术实现的关键在于网络拓扑结构的建立和高效能最短路径算法。下面我就分别从这两方面讨论起。? 2. 网络拓扑关系的建立 网络分析是空间分析的一个重要方面，是依据网络拓扑关系（线性实体之间、线性实体与结点之间、结点与结点之间的连结、联通关系），并通过考察网络元素的空间、属性数据，对网络的性能特征进行多方面的分析计算。对地理网络、城市基础设施网络进行地理分析和模型化的关键技术是用什么样的方式抽象出网络拓扑结构,及节点与节点的连通关系,并对网络拓扑结构进行高效能访问。。前者被称为网线或链（link），后者一般称为结点（node）。网线构成网络的骨架，是资源传输或通讯网络的通道，可以代表公路、铁路、航线、水管、河流等；结点是网线的端点，又是网线的交汇点，可以表示交叉路口、中转站、河流汇合点等。除了上述基本网络元素之外，网络还可能有若干附属元素，如在路径分析中用来表示途径地点的站点；在资源分配中用来表示资源发散地点或资源汇聚地点的中心；对资源传输或通讯网络起阻断作用的障碍等。针对网络分析的需要，作为网络基本元素的网线或结点除自身的常规属性外，还要具有一些特殊属性的数据。比如，为了实施路径分析和资源分配，网线数据应包含正反两个方面上的阻碍度以及资源需求量，而节点数据也应该包含资源需求量。 2.2 网络拓扑关系的获取 GIS中的数据(如道路、管网、水系等)要进行最短路径的计算,就必须首先将其按结点和边的关系抽象为图的结构,这在GIS中称为构建网络的拓扑关系。只有建立了拓扑关系,我们才能进行网络路径分析。 图2.1 拓扑关系建立过程流程图 3. 最短路径算法? 由于网络特征的复杂性和问题的不同特征，最短路径的算法也表现出多样性。但总的来说可以按问题的类型、网络特征和实现的算法进行分类，其中最经典，应用最广泛的的还是Dijkstra算法。在实际应用当中，应该根据不同问题的类型选择适合于该问题的算法。 3.1 算法选择 最短路径算法选取的原则一般包括：1.算法速度快；2.算法占用资源少；3.算法稳定性强。据统计，目前提出来的最短路径算法大约有17种，F.BenJiama等人对其中的15种进行了测试，结果显示有三种效果比较好，他们分别