空间分析报告结课报告.docxVIP

空间分析结课报告课题内容:空间分析之网络分析姓名：学号：班号：指导老师：GIS网络分析之最短路径问题的研究摘要 :网络分析作为GIS的重要功能，在各个领域都发挥着巨大的作用，而网络分析中最基础也是最重要的是最短路径问题,针对最短路径问题的研究层出不穷,本文就最短路径问题作了详细的分析并将最短路径算法中应用比较普遍的算法之一——Dijkstra算法及其优化算法进行详细分析，辅以相关实例加以说明，清楚地分析最短路径问题在网络分析中发挥的作用,展现网络分析在空间分析应用中的重要性.关键字 : GIS 空间分析网络分析最短路径问题Dijkstra算法网络拓扑结构1 前言随着科技的发展,信息时代的到来,信息化产业迅猛崛起,GIS应用已深入到人们的日常生活之中.各行各业的蓬勃发展驱动着GIS的前进,为了满足广大人民的需求,GIS产业不断扩大、优化，GIS的综合分析功能亦成为大家关注的焦点。GIS的网络空间分析功能是区别于其他的信息系统主要特征，也是GIS明显的优势之一。空间分析运用各种数学手段对地理空间数据进行操作，最终解决人们所关心的地理空间的实际问题，提取地理空间数据中所隐含的有用信息，以达到辅助决策的目的。GIS网络分析功能的主要目的是对地理网络（如交通网络）、城市基础设施网络(如各种网线、电力线、电话线、供排水管线等)进行模型化和地理分析。其主要内容是依据网络拓扑关系(线性实体之间、线性实体与结点之间、结点与结点之间的联结、连通关系) , 并通过考察网络元素的空间、属性数据, 对网络的性能特征进行多方面的分析计算。在各种GIS网络分析中, 最基本最关键的问题是最短路径问题。最短路径不仅仅指一般地理意义上的距离最短, 还可以引申到其他的度量, 如时间、费用、线路容量等。相应的, 最短路径问题就成为最快路径问题、最低费用问题等。其实, 无论是距离最短、时间最快还是费用最低, 它们的核心算法都是最短路径算法。2 最短路径问题2.1 网络分析网络的基本概念从数学的观点，GIS中的网络是图，利用图论的研究成果可以解决网络分析的众多问题。图论的术语“网络”，指的就是加权有向图。网络在数学和计算机领域中被抽象为图，所以其基础是图的存储表示。一般无向图可以用领接矩阵和邻接多重表来表示，而有向图则可以用邻接表和十字链来表示。 下图是网络图的几种数据结构的对比：网络数据模型的基本概念网络是由若干线性实体互连而成的一个系统，资源由网络来传输，实体间的联络也由网络来达成.网络数据模型是真实世界中网络系统(如交通网、通讯网、自来水管网、煤气管网等)的抽象表示.构成网络的最基本元素是上述线性实体以及这些实体的连接交汇点.前者常被称为网线或链(link)，后者一般称为结点(node).网线构成网络的骨架，是资源传输或通讯联络的通道，可以代表公路、铁路、航线、水管、煤气管、河流等；结点是网线的端点，又是网线汇合点，可以表示交叉路口、中转站、河流汇合点等. 除了上述基本网络元素之外，网络还可能有若干附属元素，如在路径分析中用来表示途经地点的可以进行资源装卸的站点(stop)；在资源分配中用来表示资源发散地点或资源汇聚地点的中心(cen_ter)，对资源传输或通讯联络起阻断作用的障碍(barrier)等.网络分析一般功能路径分析路径分析是GIS中最基本的功能，其核心是对最佳路径和最短路径的求解.从网络模型的角度看，最佳路径求解就是在指定网络中两结点间找一条阻碍强度最小的路径.最佳路径的产生基于网线和结点转角(如果模型中结点具有转角数据)的阻碍强度.资源分配资源分配就是为网络中的网线和结点寻找最近(这里的远近是按阻碍强度的大小来确定的)的中心(资源发散或汇集地).连通分析人们常常需要知道从某一结点或网线出发能够到达的全部结点或网线.这一类问题称为连通分量求解.另一连通分析问题是最少费用连通方案的求解，即在耗费最小的情况下使得全部结点相互连通.?流分析所谓流，就是将资源由一个地点运送到另一个地点.流分析的问题主要是按照某种最优化标准(时间最少、费用最低、路程最短或运送量最大等)设计运送方案.选址选址功能涉及在某一指定区域内选择服务性设施的位置，在网络分析中的选址问题一般限定设施必须位于某个结点或位于某条网线上，或者限定在若干候选地点中选择位置.2.2 最短路径问题的概述若网络中的每条边都有一个数值(长度、成本、时间等)，则找出两节点(通常是源节点和阱节点)之间总权和最小的路径就是最短路问题。最短路问题是网络理论解决的典型问题之一，可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。最短路问题，我们通常归属为三类：单源最短路径问题——包括确定起点的最短路径问题，确定终点的最短路径问题（与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与