网络图分析

第七章网络图分析主讲教师：邱春霞测绘学院•以网络为命脉，使整个区域机体生存活跃和发展。GIS把这些网络的空间分布、传输特性和规律的分析，归结为网络分析，为与现今广泛使用的其它学科的网络分析（如电路网络分析）略加区别，故把GIS中的网络分析特称为网络图分析。•在网络图分析中，主要应用集中在：①网线及附属设备的匹配和查询；②路径分析和最小生成树分析；③网络资源耗费分配；④运输方案分析。•经典的GIS都认为矢、栅数据相对比之中，叠置及三维分析栅格具有优势，缓冲区分析矢栅优劣参半，而网络分析栅格数据毫无办法，困难很大，实际上恰恰相反，地图代数的栅格方法比矢量方法更具优势。7.1路径分析•路径问题是网络图研究最充分的问题。路径与距离有关，但距离不表示通行，而路径表示通行，有“通”才能“行”，路径的长度表示通行的距离。一、最短路径问题•所谓最短路径问题是在以权表示长度的赋权图中，寻找两顶点间所有路径中权（长度）最小的路径。•这里的权是针对长度，认为长、短是评判优劣标准，相应的权可表示通行费用，这时权最小路径成了最省费用路径，即费用最佳路径。所有运输中的最优问题都与图论中的最佳路径相关，它在运筹学中有广泛的实际意义。最短路径的算法很多，但最好算法首推Dijkstra算法。（一）Dijkstra算法•矢量GIS中，广泛使用了最短路径的Dijkstra及其改良的算法。众多图论书籍上均有详细介绍。•Dijkstra算法的基本思想：是把图G的顶点集V分为S、T两类，若起点u0到某顶点x的最短通路已求出，则将x归入S，其余未求出点归入T。开始S中只有起点u0，随着程序运行通过逐个比较距离，可把T的某个顶点归入S，同样又可逐次加入其它顶点，直到所需终点v0也被加入S，程序结束。•Dijkstra算法不仅可找出最短（u0，v0）通路，而且可找到起点u0到其他任何顶点的最短通路。因此，它不仅做了所需工作，也做了不少不需做的工作，在最不利的情况下，把其余邻点做完后才最后做自己的工作。从算法优化角度而言，此算法效率不是很高。（二）地图代数的最短路径（无向图）算法）•地图代数充分利用了图数一体的栅格数据优点。其最短路径算法主要思想是视网络为具有距离刻度的连通管系统，当起点唯一注入大量高压水时，终点最先射出的水流的轨迹便是最短路径。•对于网络的动态变化，用图计量变化表示十分方便、易行，图本身的栅格数据严密地隐含了全面的拓扑数据和几何数据，其相应数据组织也无须任何特别的安排，本算法效率高，且特别适应动态变化。•地图代数的网络图分析中，路径距离均采用栅格路径距离，一个方向上的长度是由这样5个斜率的方向组成：0,1/4,1/2,3/4,1。如前述，由这些方向的尺度组成的整数线性组合可使一个方向的欧氏长度误差小于1%，由于地图（或地理空间中）上很少在一个方向有较长直线段（大于100），而对曲线的路径无疑是较为精密，因而可较好地保证路径的欧氏长度精度。无向图最短路径基本算法步骤：•已知条件为：区域网络图G，其上边均为单像元宽、八方向连接。若不满足，则细化处理；•染G为黑色，标出起点u0为黄色点，终点v0为红色点，并记u0点的累积路径距离为0，放入升序的结点数组，该数组数据项为列号（x）、行号（y）及距离z；•取结点数组中的首结点作为起算点，若无，转步骤6；若有，与终点坐标比较，相同转步骤7，否则转步骤4；•定位该位置，按八邻域找相邻通道，若有，转步骤5，若无，则从结点数组中除去本结点后转步骤3；•不断染相邻点（非结点）黑色为绿，并按起算点标记该绿点距离，返回步骤5；•“无相邻路径”，运算结束；•标出红点，且按连通回溯，搜索相邻最速下降距离的像元，并标以红色直至u0时结束，回溯路线即是最短路径，运算结束。由算法可以明确得到结论：该回溯的最短路径上，任两个结点间距离是最短的。三、算法分析•一般路径距离数据均来自地形图或地图，并与该比例尺精度相当。因此本算法直接使用地图数据，基础精度不低于其他算法。为优化效率，采用5种尺度作为基底，计算任一方向线段距离，其最弱方向误差低于1%，累积绝对误差需另行具体统计。1、精度分析•若需再提高精度，可适当增加长度基底，即在原5个斜率方向距离为真，增加1/8、3/8、5/8、7/8斜率方向为真，将可使相对误差低于0.2%。若是再增加8个方向的距离为真，即斜率1/16、3/16、5/16、7/16、9/16、11/16、13/16、15/16方向，那么最大误差方向上的距离相对误差小于0.05%。这样，对于折线路径，精度不亚于矢量算法，曲线路径由于矢量。2、效率分析•下图为一幅1：5万5000×4000的栅格图，在低档微机上运行，无明显等待，可准实时完成。无向图最短路径（街道口到客运港的最短路径）•算法耗时主要决定于路径距离的像元数，其次决定于起、终点间各层次的结点数、通路数、长度及图的大小。本算法中的图为单像元宽，按图面极限载负量20%，交通要素占图面10%，线均宽为5像元计算，按路径跑完全部像元极限计算为8万/图，运算简单，计算量小，一般均可实时完成，本算法效率高。3、算法有理想的动态性•栅格数据的位数据可自适应于网络的动态变化，且本身隐含了全部的拓扑数据，无须任何拓扑数据及各边距离（权）数的复杂组织，动态性好，适应于任何网络的动态变化。•对于网络图的堵塞、中断、改道等变化，只需载地理信息系统中进行标记即可完成，算法本身不受任何影响。四、有向图及加权路径算法•在无向图算法基础上，对单向图边增加相邻2个色点标记：棕、紫。染色增加黑——棕——紫，绿色通过，黑——紫棕——棕返回，即可完成有向图运算。有向图最短路径•对于赋权图，原则上仅需在相应边的距离累计中乘以该边权数，即相应改进距离的数值标记，算法类同。