空间网络分析精选PPT.ppt

《空间网络分析精选PPT.ppt》由会员分享，可在线阅读，更多相关《空间网络分析精选PPT.ppt（46页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、空间网络分析第1页，此课件共46页哦网络模型第2页，此课件共46页哦1网络分析的基本概念网络分析的基本概念 网络网络是一个由点、线的二元关系构成的系统，通常用来描是一个由点、线的二元关系构成的系统，通常用来描述某种资源或物质沿着路径在空间上的运动。述某种资源或物质沿着路径在空间上的运动。在在GISGIS中，中，网络分析网络分析则是依据网络拓扑关系（线性实体之间、则是依据网络拓扑关系（线性实体之间、线性实体与结点之间、结点与结点之间的连接、连通关系），线性实体与结点之间、结点与结点之间的连接、连通关系），通过考察网络元素的空间及属性数据，以数学理论模型为基础，通过考察网络元素的空间及属性数据，以

2、数学理论模型为基础，对网络的性能特征进行多方面的一种分析计算。其中，对网络的性能特征进行多方面的一种分析计算。其中，网络图网络图论与数学模型论与数学模型是网络分析的重要理论基础。是网络分析的重要理论基础。目前，网络分析在电子导航、交通旅游、城市规划管理以及目前，网络分析在电子导航、交通旅游、城市规划管理以及电力、通讯等各种管网管线的布局设计中发挥了重要的作用。电力、通讯等各种管网管线的布局设计中发挥了重要的作用。第3页，此课件共46页哦例子20V5V0V4V1V3V210060301010505有向网络有向网络邻接矩阵邻接矩阵第4页，此课件共46页哦网络的数据结构网络的数据结构1）几何结构：表

3、示地理分布位置，用点、线表示2）拓扑结构：表示连接性，用图表示第5页，此课件共46页哦图的定义：顶点顶点 无序无序边无向图无向图顶点 有序弧有向图 有权重有权重网络网络GIS要进行网络分析，首先需要解决网络的表达和存储要进行网络分析，首先需要解决网络的表达和存储要进行网络分析，首先需要解决网络的表达和存储要进行网络分析，首先需要解决网络的表达和存储问题。问题。问题。问题。图或网络的表达：边（弧、链）、点图或网络的存储：邻接矩阵图或网络的存储：邻接矩阵第6页，此课件共46页哦1 1 1 1、链（、链（、链（、链（LinkLinkLinkLink）网络中流动的管线网络中流动的管线如街道、河流、水管

4、，如街道、河流、水管，其状态属性包括阻力和其状态属性包括阻力和需求。需求。2.1 图或网络的表达：2 2 2 2、结点（、结点（、结点（、结点（NodeNodeNodeNode）网络中链的结点，如港口、车站等，其状态属性包括阻力和网络中链的结点，如港口、车站等，其状态属性包括阻力和需求等。需求等。第7页，此课件共46页哦GISGIS要进行网络分析，首先需要解决网络的表达和存储问题。某要进行网络分析，首先需要解决网络的表达和存储问题。某局部道路网络如图局部道路网络如图2 2所示，所示，p1p1p9p9是结点编号，括号中的数字是是结点编号，括号中的数字是道路阻强道路阻强 第8页，此课件共46页哦1

5、 1）结结点点p5p5是是一一公公共共汽汽车车站站点点，平平均均每每天天上上车车人人数数为为200200人人，下车人数为下车人数为300300人，具体表达为：人，具体表达为：结点号结点号上载需求量（人）上载需求量（人）下载需求量（人）下载需求量（人）P5P5200200300300第9页，此课件共46页哦 2)2)道道路路p1p7p1p7是是一一双双行行道道，且且正正向向阻阻强强为为4040km/skm/s，负负向向阻阻强强为为3535km/skm/s，具体表达为具体表达为链链 弧弧号号起起 结结点点终终 结结点点正正 方方 向向 阻阻 强强（km/skm/s）反反 方方 向向 阻阻 强强（k

6、m/skm/s）p1p7p1p71 17 7404035353 3）道路）道路p6p8p6p8是一单行道，且阻强为是一单行道，且阻强为2020km/skm/s，具体表达为：具体表达为：链弧号链弧号起结点起结点终终 结结点点正正 方方 向向 阻阻 强强（km/skm/s）反反 方方 向向 阻阻 强强（km/skm/s）P6p8P6p86 68 82020-1(-1(表不通表不通)第10页，此课件共46页哦结点中的特殊类型 障碍（障碍（BarrierBarrier），），禁止网络上流动的点。禁止网络上流动的点。拐点（拐点（TurnTurn），），出现在网络中的分割点上，其状态有属性和阻力，出现在网

7、络中的分割点上，其状态有属性和阻力，如拐弯的时间和限制（如在如拐弯的时间和限制（如在8 8点到点到1818点不允许左拐）。点不允许左拐）。中心（中心（CenterCenter），），是接受或分配资源的位置，如水库、商业中心，是接受或分配资源的位置，如水库、商业中心，电站等，其状态包括资源容量（如总量），阻力限额（中心到电站等，其状态包括资源容量（如总量），阻力限额（中心到链的最大距离或时间）。链的最大距离或时间）。站点（站点（StopStop），），在路径选择中资源增减的结点，如库房、车站等，在路径选择中资源增减的结点，如库房、车站等，其状态属性有资源需求，如产品数量。其状态属性有资源需求，如

8、产品数量。第11页，此课件共46页哦拐点拐点第12页，此课件共46页哦转弯类型描述属性表0=无阻强-1=不允许拐弯U型拐弯指从6号弧至20号结点并从20号结点转回6号弧，这是一个180度转弯，花费20秒时间停靠点使得从6号弧至其他弧段直到 7 号弧，向左转至8号弧，向右转至9号弧的运移减慢不允许从6号弧转至9号弧，并赋予负值阻强；允许其他方向的转变，其阻强为正高架道或地道允许直通而无延迟，如从6号弧至7号弧；但不允许转弯，此时以负的阻强表示，如从6号弧至8、9号弧968720U型转弯角度至弧段从弧段结点号时间阻强/s968720高架道或地道968720停靠点968720不准转弯66202007

9、6201590862020-909620101807620008620-1909620-1-909620-1-9076205086201090第13页，此课件共46页哦2.2 图或网络的存储 P170邻接矩阵无向图、有向图 有向网络1、0 1、&、0第14页，此课件共46页哦3空间网络分析的方法空间网络分析的方法3.1路径分析v最短路径分析最短路径分析v连通性分析-最小生成树3.2中心选址第15页，此课件共46页哦 3.1.1 3.1.1 最短路径求解最短路径求解v最短路径求解有多种不同的方法，其中最短路径求解有多种不同的方法，其中DijkstraDijkstra算法适合于求解某个起点（源点）

10、到网络中的其它各个结点的最佳路径。第16页，此课件共46页哦例子例子20V5V0V4V1V3V210060301010505有向网络有向网络第17页，此课件共46页哦例子例子(思路思路)ACiBi 如图所示，如图所示，A A为所求最短距离的起点，其他为所求最短距离的起点，其他Bi,Ci Bi,Ci 为终点。为终点。目的目的:求求一系列最短距离一系列最短距离。我们先假定这些最。我们先假定这些最短距离互不相等。那么我们可以把这些最短距短距离互不相等。那么我们可以把这些最短距离按升序（从小到大）排列离按升序（从小到大）排列步骤步骤:我们把所有顶点分为两类我们把所有顶点分为两类C C和和B.B.令令A

11、 A到到BiBi这些这些顶点的最短距离顶点的最短距离不为无穷大不为无穷大,A A到到CiCi这些顶点的最这些顶点的最短距离为短距离为无穷大无穷大 这就说明这就说明A A到到CiCi中的点要么不通，要么通过中的点要么不通，要么通过BiBi中的点与之连接。中的点与之连接。第18页，此课件共46页哦例子(思路)ACiBi 这样，对于这样，对于A A到到CiCi中任何一个点中任何一个点的最小距离，我们总可以在的最小距离，我们总可以在BiBi中找到中找到一点，使得一点，使得A A到这一点的最小距离小于到这一点的最小距离小于前一个距离。（因为前一个距离。（因为A A到到CiCi中的点要中的点要么不通，要么

12、通过么不通，要么通过BiBi中的点与之连中的点与之连通。通。）因此，我们可以先不考虑因此，我们可以先不考虑CiCi中中的点。的点。第19页，此课件共46页哦例子(思路)于是，对于右图，我们第一步只考虑于是，对于右图，我们第一步只考虑下图下图:V5V0V4V21003010Bi=v2,v4,v520V5V0V4V1V3V210060301010505第20页，此课件共46页哦例子(思路)我们用我们用我们用我们用mindistmindistmindistmindist这个数组来保存由这个数组来保存由这个数组来保存由这个数组来保存由v0v0v0v0到其它顶点的最小距离，这些距离按升到其它顶点的最小距

13、离，这些距离按升到其它顶点的最小距离，这些距离按升到其它顶点的最小距离，这些距离按升序排列。序排列。序排列。序排列。考虑右图：考虑右图：考虑右图：考虑右图：第一步，通过比较，我们知道第一步，通过比较，我们知道第一步，通过比较，我们知道第一步，通过比较，我们知道 mindistancev0v2=mindist0=10,mindistancev0v2=mindist0=10,mindistancev0v2=mindist0=10,mindistancev0v2=mindist0=10,（v0-v2)v0-v2)v0-v2)v0-v2)这是我们求出的第一个最小距离这是我们求出的第一个最小距离这是我们

14、求出的第一个最小距离这是我们求出的第一个最小距离一旦我们得到一旦我们得到v2v2，我们就可以知道：我们就可以知道：V5V0V4V21003010向量第21页，此课件共46页哦例子例子(思路思路)V0V0跟跟 v2v2直接连通到的点直接连通到的点v3v3 之间的最之间的最小距离不再是无穷大，它应当是小距离不再是无穷大，它应当是mindistancev0v2+disv2vmindistancev0v2+disv2v3,3,这样我们应当把这样我们应当把v3v3放入前面的集合放入前面的集合BiBi中。中。（注意：有多少（注意：有多少v2v2直接连通到的点直接连通到的点都都应当考虑进来。）应当考虑进来。

15、）V5V0V4V3V2100301050Bi=v2,v4,v5,v3第22页，此课件共46页哦例子例子(思路思路)第二步，我们把与第二步，我们把与v2v2直接连通的点直接连通的点v3v3考虑进考虑进来。来。dis05=100;dis04=30;dis05=100;dis04=30;dis02=10;dis03=60;dis02=10;dis03=60;除除1010以外，以外，3030是最小的。是最小的。我们可以证明我们可以证明3030是是v0v0到其它顶点到其它顶点除除1010以外最小的。以外最小的。V5V0V4V3V2100301050向量第23页，此课件共46页哦例子(思路)这样我们得到我

16、们的第二个最小距离：这样我们得到我们的第二个最小距离：Mindistancev0v4=mindist1=30,(v0-v4)Mindistancev0v4=mindist1=30,(v0-v4)接下来，我们把接下来，我们把v4v4与之直接连通的点与之直接连通的点考虑考虑进来。进来。V5V0V4V3V2100301050Bi第24页，此课件共46页哦例子例子以v0为起点，计算它到其它各顶点的最短路径，计算过程中最短路径长度向量D的变化见D0-D4，计算出的各条最短路径。第25页，此课件共46页哦例子20V5V0V4V1V3V210060301010505有向网络有向网络第26页，此课件共46页哦

17、V0V1V2V3V4V5V0V0为起始点为起始点为起始点为起始点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页哦例子起点起点终点终点最短路径最短路径路路径径长长度度v0v1无无v2(v0,v2)10v3(v0,v4,v3)50v4(v0,v4)30v5(v0,v4,v3,v5)60第28页，此课件共46页哦20V5V0V4V1V3V210060301010505带权有向图带权

18、有向图作业1:求V0到到V5的最短路径的最短路径第29页，此课件共46页哦V0V1V2V3V4V5V0V0为起始点为起始点为起始点为起始点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页哦起点起点终点终点最短路径最短路径路路径径长长度度v0v1无无v2(v0,v2)10v3(v0,v3)30v4无无v5(v0,v3,v5)40第31页，此课件共46页哦规律规律(步骤步骤)制作制作制作制作N

19、*N的矩阵的矩阵的矩阵的矩阵第第m行就意味着有行就意味着有mm个值个值个值个值(距离距离距离距离)已经确定已经确定已经确定已经确定在确定一个点后在确定一个点后,与该点相邻接的点的距离重新计算与该点相邻接的点的距离重新计算,与该点不相邻的则保持不变与该点不相邻的则保持不变(直接照抄之前的直接照抄之前的)在重新计算点的距离时在重新计算点的距离时,只要考虑与该点相邻的只要考虑与该点相邻的所有点的所有点的最短距离最短距离.第32页，此课件共46页哦v6v8v1v7v5v4v2v389363253757作业2:求V1到其他各点的最短路径到其他各点的最短路径第33页，此课件共46页哦V1V1V2V2V3V

20、3V4V4V5V5V6V6V7V7V8V8V1V1为起始点为起始点0 0(9)(9)(&)(&)(&)(&)(&)(&)(6)(6)(3)(3)(8)(8)V17=3V17=30 0(9)(9)(&)(&)(&)(&)(8)(8)(6)(6)3 3(8)(8)V16=6V16=60 0(9)(9)(&)(&)(&)(&)(8)(8)6 63 3(8)(8)V15=8V15=80 0(9)(9)(&)(&)(15)(15)8 86 63 3(8)(8)V18=8V18=80 0(9)(9)(&)(&)(15)(15)8 86 63 38 8V12=9V12=90 09 9(14)(14)(12)

21、(12)8 86 63 38 8V14=12V14=120 09 9(14)(14)12128 86 63 38 8V13=14V13=140 09 9141412128 86 63 38 8第34页，此课件共46页哦3.1.2 连通性分析-最小生成树（1）概念连通图：在一个图中，任意两个节点之间都存在一条路。树：若一个连通图中不存在任何回路，则称为树。生成树的权数：生成树中各边的权数之和。最小生成树：图的极小连通子图。（2 2）应用：通信线路、快递）应用：通信线路、快递56第35页，此课件共46页哦（3）构造最小生成树的依据依据：v在网中选择N-1N-1条边连接网的N个顶点v尽可能选取权值为

22、最小的边3.1.2 连通性分析-最小生成树第36页，此课件共46页哦(4)(4)算法（算法（KruskalKruskal，克罗斯克尔算法，也叫克罗斯克尔算法，也叫“避圈避圈”法）法）1 1）先把图中的各边按权数从小到大重新排列，并取权数最）先把图中的各边按权数从小到大重新排列，并取权数最小的一条边为最小生成树中的边。小的一条边为最小生成树中的边。2 2）在剩下的边中，按顺序取下一条边。若该边与最小生成）在剩下的边中，按顺序取下一条边。若该边与最小生成树中已有的边，构成回路，则舍去该边，否则选中生成树。树中已有的边，构成回路，则舍去该边，否则选中生成树。3 3）重复）重复2 2），直到有），直到

23、有M-1M-1条边被选进生成树中，这条边被选进生成树中，这M-1M-1条边就构条边就构成最小生成树成最小生成树3.1.2 连通性分析-最小生成树第37页，此课件共46页哦3.1.2 连通性分析-最小生成树具体步骤具体步骤第38页，此课件共46页哦请请应应用用克克罗罗斯斯克克尔尔算算法法确确定定下下图图的的最最小小生生成成树树（含含步骤）。步骤）。12345647710131718152228作业：作业：第39页，此课件共46页哦894612752715V6V1V2V3V4V5V7第40页，此课件共46页哦4.2 中心选址问题 中心点选址问题中，最佳选址位置的判定标准，是使其所在的顶点与图中其它

24、顶点之间的最大距离达到最小，或者使其所在的顶点到图中其它顶点之间的距离之和达到最小。这个选址问题实际上就是求网络图的中心点问题。这类选址问题适宜于医院、消防站等服务设施的布局问题。第41页，此课件共46页哦v6v8v1v7v5v4v2v389363253757中心选址问题的实例例如，某县要在其所辖的8个乡镇之一修建一个消防站，为8个乡镇服务，要要求求消消防防站站至至最最远远乡乡镇镇的的距距离离达达到到最最小小。假设该8个乡镇之间的交通网络被抽象为无向赋权连通图，权值为乡镇之间的距离。下面求解消防站应设在哪个乡镇，即哪个顶点？第42页，此课件共46页哦首先，用首先，用DijkstraDijkst

25、ra算法计算出算法计算出每一个顶点每一个顶点每一个顶点每一个顶点v vi i至其它各顶点至其它各顶点v vj j的的最短路径长度最短路径长度d dijij(i i,j j=1,2,=1,2,6),6)，写出距离矩阵：写出距离矩阵：中心选址问题的实例6061916152565473第43页，此课件共46页哦其其次次，求求距距离离矩矩阵阵中中每每行行的的最最大大值值，即即各各个个顶顶点点的的最最大大服服务务距距离离，得得e e(v v1 1)=14,)=14,e e(v v2 2)=15,)=15,e e(v v3 3)=20,)=20,e e(v v4 4)=12,)=12,e e(v v5 5

26、)=15,)=15,e e(v v6 6)=17,)=17,e e(v v7 7)=12,)=12,e e(v v8 8)=20)=20最最后后计计算算最最大大服服务务距距离离的的最最小小值值。显显然然，e e(v v4 4)=e e(v v7 7)=minmin e e(v vi i)。所以，所以，消防站应建在消防站应建在消防站应建在消防站应建在v v v v4 4 4 4或或或或v v v v7 7 7 7点所在的乡镇点所在的乡镇点所在的乡镇点所在的乡镇。中心选址问题的实例第44页，此课件共46页哦6061916152565473要求消防站至要求消防站至所有所有乡镇的距离达到最小乡镇的距离达到最小：中心选址问题的实例消防站应建在消防站应建在消防站应建在消防站应建在v v v v5 5 5 5点所在的乡镇点所在的乡镇点所在的乡镇点所在的乡镇第45页，此课件共46页哦第46页，此课件共46页哦