空间网络分析

空间网络分析第1页，课件共46页，创作于2023年2月网络模型第2页，课件共46页，创作于2023年2月1．网络分析的基本概念

网络是一个由点、线的二元关系构成的系统，通常用来描述某种资源或物质沿着路径在空间上的运动。在GIS中，网络分析则是依据网络拓扑关系（线性实体之间、线性实体与结点之间、结点与结点之间的连接、连通关系），通过考察网络元素的空间及属性数据，以数学理论模型为基础，对网络的性能特征进行多方面的一种分析计算。其中，网络图论与数学模型是网络分析的重要理论基础。目前，网络分析在电子导航、交通旅游、城市规划管理以及电力、通讯等各种管网管线的布局设计中发挥了重要的作用。第3页，课件共46页，创作于2023年2月例子20V5V0V4V1V3V210060301010505有向网络邻接矩阵第4页，课件共46页，创作于2023年2月网络的数据结构1）几何结构：表示地理分布位置，用点、线表示2）拓扑结构：表示连接性，用图表示第5页，课件共46页，创作于2023年2月图的定义：顶点无序——边——无向图顶点有序——弧——有向图有权重——网络GIS要进行网络分析，首先需要解决网络的表达和存储问题。图或网络的表达：边（弧、链）、点图或网络的存储：邻接矩阵第6页，课件共46页，创作于2023年2月1、链（Link）网络中流动的管线如街道、河流、水管，其状态属性包括阻力和需求。2.1图或网络的表达：2、结点（Node）网络中链的结点，如港口、车站等，其状态属性包括阻力和需求等。第7页，课件共46页，创作于2023年2月GIS要进行网络分析，首先需要解决网络的表达和存储问题。某局部道路网络如图2所示，p1…p9是结点编号，括号中的数字是道路阻强

第8页，课件共46页，创作于2023年2月1）结点p5是一公共汽车站点，平均每天上车人数为200人，下车人数为300人，具体表达为：结点号

上载需求量（人）

下载需求量（人）

P5200300第9页，课件共46页，创作于2023年2月2)道路p1p7是一双行道，且正向阻强为40km/s，负向阻强为35km/s，具体表达为链弧号起结点终结点正方向阻强（km/s）反方向阻强（km/s）p1p7174035

3）道路p6p8是一单行道，且阻强为20km/s，具体表达为：链弧号起结点终结点正方向阻强（km/s）反方向阻强（km/s）P6p86820-1(表不通)第10页，课件共46页，创作于2023年2月结点中的特殊类型障碍（Barrier），禁止网络上流动的点。拐点（Turn），出现在网络中的分割点上，其状态有属性和阻力，如拐弯的时间和限制（如在8点到18点不允许左拐）。中心（Center），是接受或分配资源的位置，如水库、商业中心，电站等，其状态包括资源容量（如总量），阻力限额（中心到链的最大距离或时间）。站点（Stop），在路径选择中资源增减的结点，如库房、车站等，其状态属性有资源需求，如产品数量。

第11页，课件共46页，创作于2023年2月拐点第12页，课件共46页，创作于2023年2月

转弯类型

描

述

属性表0=无阻强-1=不允许拐弯U型拐弯指从6号弧至20号结点并从20号结点转回6号弧，这是一个180度转弯，花费20秒时间停靠点使得从6号弧至其他弧段——直到7号弧，向左转至8号弧，向右转至9号弧的运移减慢不允许从6号弧转至9号弧，并赋予负值阻强；允许其他方向的转变，其阻强为正高架道或地道允许直通而无延迟，如从6号弧至7号弧；但不允许转弯，此时以负的阻强表示，如从6号弧至8、9号弧968720U型转弯角度至弧段从弧段结点号时间阻强/s968720高架道或地道968720停靠点968720不准转弯662020076201590862020-909620101807620008620-1909620-1-909620-1-9076205086201090第13页，课件共46页，创作于2023年2月2.2图或网络的存储P170邻接矩阵无向图、有向图有向网络1、01、&、0第14页，课件共46页，创作于2023年2月

3．空间网络分析的方法3.1路径分析最短路径分析连通性分析------最小生成树3.2中心选址第15页，课件共46页，创作于2023年2月3.1.1最短路径求解最短路径求解有多种不同的方法，其中Dijkstra算法适合于求解某个起点（源点）到网络中的其它各个结点的最佳路径。第16页，课件共46页，创作于2023年2月例子20V5V0V4V1V3V210060301010505有向网络第17页，课件共46页，创作于2023年2月例子(思路)ACiBi如图所示，A为所求最短距离的起点，其他Bi,Ci为终点。目的:求一系列最短距离。我们先假定这些最短距离互不相等。那么我们可以把这些最短距离按升序（从小到大）排列步骤:我们把所有顶点分为两类C和B.令A到Bi这些顶点的最短距离不为无穷大,A到Ci这些顶点的最短距离为无穷大

这就说明A到Ci中的点要么不通，要么通过Bi中的点与之连接。

第18页，课件共46页，创作于2023年2月例子(思路)ACiBi

这样，对于A到Ci中任何一个点的最小距离，我们总可以在Bi中找到一点，使得A到这一点的最小距离小于前一个距离。（因为A到Ci中的点要么不通，要么通过Bi中的点与之连通。）因此，我们可以先不考虑Ci中的点。第19页，课件共46页，创作于2023年2月例子(思路)于是，对于右图，我们第一步只考虑下图:V5V0V4V21003010Bi={v2,v4,v5}20V5V0V4V1V3V210060301010505第20页，课件共46页，创作于2023年2月例子(思路)我们用mindist[]这个数组来保存由v0到其它顶点的最小距离，这些距离按升序排列。

考虑右图：第一步，通过比较，我们知道mindistance[v0][v2]=mindist[0]=10,（v0-v2)这是我们求出的第一个最小距离一旦我们得到v2，我们就可以知道：V5V0V4V21003010向量第21页，课件共46页，创作于2023年2月例子(思路)V0跟v2直接连通到的点v3

之间的最小距离不再是无穷大，它应当是mindistance[v0][v2]+dis[v2][v3],这样我们应当把v3放入前面的集合Bi中。（注意：有多少v2直接连通到的点都应当考虑进来。）V5V0V4V3V2100301050Bi={v2,v4,v5,v3}第22页，课件共46页，创作于2023年2月例子(思路)第二步，我们把与v2直接连通的点v3考虑进来。dis[0][5]=100;dis[0][4]=30;dis[0][2]=10;dis[0][3]=60;除10以外，30是最小的。我们可以证明30是v0到其它顶点除10以外最小的。V5V0V4V3V2100301050向量第23页，课件共46页，创作于2023年2月例子(思路)这样我们得到我们的第二个最小距离：Mindistance[v0][v4]=mindist[1]=30,(v0-v4)接下来，我们把v4与之直接连通的点考虑进来。。。V5V0V4V3V2100301050Bi第24页，课件共46页，创作于2023年2月例子

以v0为起点，计算它到其它各顶点的最短路径，计算过程中最短路径长度向量D的变化见D0-D4，计算出的各条最短路径。第25页，课件共46页，创作于2023年2月例子20V5V0V4V1V3V210060301010505有向网络第26页，课件共46页，创作于2023年2月V0V1V2V3V4V5V0为起始点0(&)(10)(&)(30)(100)V02=100(&)10(60)(30)(100)V04=300(&)10(50)30(90)V03=500(&)105030(60)V05=600(&)10503060V01=&0&1050306012第27页，课件共46页，创作于2023年2月例子起点终点最短路径路径长度v0v1无

v2(v0,v2)10

v3(v0,v4,v3)50

v4(v0,v4)30

v5(v0,v4,v3,v5)60第28页，课件共46页，创作于2023年2月20V5V0V4V1V3V210060301010505带权有向图作业1:求V0到V5的最短路径第29页，课件共46页，创作于2023年2月V0V1V2V3V4V5V0为起始点0(&)(10)(30)(&)(100)V02=100(&)10(30)(&)(100)V03=300(&)1030(&)(40)V05=400(&)1030(&)40V01=&0&1030(&)40V04=&0&1030&4012第30页，课件共46页，创作于2023年2月起点终点最短路径路径长度v0v1无

v2(v0,v2)10

v3(v0,v3)30

v4无

v5(v0,v3,v5)40第31页，课件共46页，创作于2023年2月规律(步骤)制作N*N的矩阵第m行就意味着有m个值(距离)已经确定在确定一个点后,与该点相邻接的点的距离重新计算,与该点不相邻的则保持不变(直接照抄之前的)在重新计算点的距离时,只要考虑与该点相邻的所有点的最短距离.……第32页，课件共46页，创作于2023年2月v6v8v1v7v5v4v2v389363253757作业2:求V1到其他各点的最短路径第33页，课件共46页，创作于2023年2月V1V2V3V4V5V6V7V8V1为起始点0(9)(&)(&)(&)(6)(3)(8)V17=30(9)(&)(&)(8)(6)3(8)V16=60(9)(&)(&)(8)63(8)V15=80(9)(&)(15)863(8)V18=80(9)(&)(15)8638V12=909(14)(12)8638V14=1209(14)128638V13=140914128638第34页，课件共46页，创作于2023年2月3.1.2连通性分析----最小生成树（1）概念连通图：在一个图中，任意两个节点之间都存在一条路。树：若一个连通图中不存在任何回路，则称为树。生成树的权数：生成树中各边的权数之和。最小生成树：图的极小连通子图。（2）应用：通信线路、快递56第35页，课件共46页，创作于2023年2月（3）构造最小生成树的依据：在网中选择N-1条边连接网的N个顶点尽可能选取权值为最小的边3.1.2连通性分析----最小生成树第36页，课件共46页，创作于2023年2月(4)算法（Kruskal，克罗斯克尔算法，也叫“避圈”法）1）先把图中的各边按权数从小到大重新排列，并取权数最小的一条边为最小生成树中的边。2）在剩下的边中，按顺序取下一条边。若该边与最小生成树中已有的边，构成回路，则舍去该边，否则选中生成树。3）重复2），直到有M-1条边被选进生成树中，这M-1条边就构成最小生成树3.1.2连通性分析----最小生成树第37页，课件共46页，创作于2023年2月3.1.2连通性分析----最小生成树具体步骤第38页，课件共46页，创作于2023年2月请应用克罗斯克尔算法确定下图的最小生成树（含步骤）。12345647710131718152228作业：第39页，课件共46页，创作于2023年2月894612752715V6V1V2V3V4V5V7第40页，课件共46页，创作于2023年2月4.2中心选址问题中心点选址问题中，最佳选址位置的判定标准，是使其所在的顶点与图中其它顶点之间的最大距离达到最小，或者使其所在的顶点到图中其它顶点之间的距离之和达到最小。这个选址问题实际上就是求网络图的中心点问题。这类选址问题适宜于医院、消防站等服务设施的布局问题。

第41页，课件共46页，创作于2023年2月v6v8v1v7v5v4v2v38936325375