网络图分析.ppt

第七章第七章网络图分析网络图分析主讲教师:邱春霞主讲教师:邱春霞测绘学院测绘学院 1 1 ?以网络为命脉,使整个区域机体生存活跃和发展。 GIS 把这些网络的空间分布、传输特性和规律的分析,归结为网络分析,为与现今广泛使用的其它学科的网络分析(如电路网络分析)略加区别, 故把 GIS 中的网络分析特称为网络图分析。?在网络图分析中,主要应用集中在:①网线及附属设备的匹配和查询; ②路径分析和最小生成树分析; ③网络资源耗费分配; ④运输方案分析。 2 2 ?经典的 GIS 都认为矢、栅数据相对比之中, 叠置及三维分析栅格具有优势,缓冲区分析矢栅优劣参半,而网络分析栅格数据毫无办法,困难很大,实际上恰恰相反, 地图代数的栅格方法比矢量方法更具优势。 3 3 路径分析路径分析?路径问题是网络图研究最充分的问题。路径与距离有关,但距离不表示通行,而路径表示通行,有“通”才能“行”,路径的长度表示通行的距离。 4 4 一、最短路径问题一、最短路径问题?所谓最短路径问题是在以权表示长度的赋权图中,寻找两顶点间所有路径中权(长度)最小的路径。?这里的权是针对长度,认为长、短是评判优劣标准,相应的权可表示通行费用,这时权最小路径成了最省费用路径,即费用最佳路径。所有运输中的最优问题都与图论中的最佳路径相关,它在运筹学中有广泛的实际意义。最短路径的算法很多,但最好算法首推 Dijkstra 算法。 5 5 (一) (一) Dijkstra Dijkstra 算法算法?矢量 GIS 中,广泛使用了最短路径的 Dijkstra 及其改良的算法。众多图论书籍上均有详细介绍。? Dijkstra 算法的基本思想:是把图 G的顶点集 V 分为 S、T两类,若起点 u 0到某顶点 x的最短通路已求出,则将 x归入 S,其余未求出点归入 T。开始 S中只有起点 u 0,随着程序运行通过逐个比较距离,可把 T的某个顶点归入 S,同样又可逐次加入其它顶点,直到所需终点 v 0也被加入 S, 程序结束。 6 6 ? Dijkstra 算法不仅可找出最短( u 0,v 0)通路, 而且可找到起点 u 0到其他任何顶点的最短通路。因此, 它不仅做了所需工作,也做了不少不需做的工作, 在最不利的情况下,把其余邻点做完后才最后做自己的工作。从算法优化角度而言,此算法效率不是很高。 7 7 (二)地图代数的最短路径(无向图)算(二)地图代数的最短路径(无向图)算法) 法) ?地图代数充分利用了图数一体的栅格数据优点。其最短路径算法主要思想是视网络为具有距离刻度的连通管系统,当起点唯一注入大量高压水时,终点最先射出的水流的轨迹便是最短路径。 8 8 ?对于网络的动态变化,用图计量变化表示十分方便、易行,图本身的栅格数据严密地隐含了全面的拓扑数据和几何数据,其相应数据组织也无须任何特别的安排, 本算法效率高,且特别适应动态变化。 9 9 ?地图代数的网络图分析中, 路径距离均采用栅格路径距离,一个方向上的长度是由这样 5个斜率的方向组成: 0,1/4,1/2,3/4,1 。如前述,由这些方向的尺度组成的整数线性组合可使一个方向的欧氏长度误差小于 1% ,由于地图(或地理空间中)上很少在一个方向有较长直线段(大于 100 ),而对曲线的路径无疑是较为精密,因而可较好地保证路径的欧氏长度精度。 10 10