石大地理信息系统课件第5章 空间分析原理与方法

（★重点、难点）参考书郭仁忠著刘湘南黄方王平第一节空间分析概述第二节数字地形模型分析第三节空间叠合分析第四节空间邻近度分析第五节空间网络分析主要内容：第一节空间分析概述空间分析是GIS的核心功能和重要组成部分；空间分析的概念是基于空间数据的分析技术，以地球科学原理为依托，通过分析算法，从空间数据中获取有关地理对象的空间位置、空间分布、空间形态、空间形成和空间演变等信息；目的：通过数据深加工，获取新的地理信息；空间分析的分类按照空间数据的形式分为:矢量数据空间分析：矢量叠合分析、矢量邻近性分析、网络分析等；栅格数据空间分析：DTM和DEM分析、栅格叠合分析、栅格邻近性分析、栅格统计分析等；第一节空间分析概述第一节空间分析概述空间分析的分类按照Goodchild提出的空间分析框架分为：产生式分析：DTM分析、叠合分析、空间临近性分析、网络分析和空间统计分析；查询式分析：空间集合分析和空间数据查询第二节数字地形模型分析基本概念DEM的建立数字地形分析1.DTM与DEM数字地面模型（DTM）和数字高程模型（DEM）是GIS空间数据库中最重要的空间信息资料，是进行GIS三维分析的核心数据系统，其基本理论与数据处理方法全面反映了GIS空间分析的基本方法；1.1DTM(数字地面模型DigitalTerrainModels)定义：DTM是对某种或多种地面特性空间分布的数学描述，是叠加在二维地理空间上的地面特性向量空间，是对地表属性的三维特征的一种描述;1.DTM与DEMKp为第p个地面点（或地表单元）上的第k类地面特性信息的取值，是二维表面上连续变化的地理特征，如地面温度、降雨、地球磁力、重力、土地利用、土壤类型等地面特征；(up,vp)为第p个地面点的二维坐标，可以是平面坐标、经纬度、矩阵行列号;m为地面特性信息的数目，n为地面点的个数;1.1DTM(DigitalTerrainModels)1.1DTM(DigitalTerrainModels)定义：当DTM中的地面属性信息仅有一种——海拔高程，那么此时的DTM就是DEM，它是地表单元上高程的集合;DEM是DTM的一个子集，也是DTM中最基本的部分，它是对地球表面地形地貌的一种数字表达;★DigitalElevationModels)1.2DEM

(数字高程模型中国DEM新疆DEMDigitalElevationModels)1.2DEM

(数字高程模型1.2.1DEM的表现形式等高线法规则格网（Grid）不规则三角网（TIN）(1)等高线法等高线通常被存储成有序的坐标点序列，是一条带有高程值属性的简单多边形或多边形弧段；等高线模型只表达区域的部分高程值，故需要通过插值方法来计算等高线以外其他点的高程；又因为这些点是落在两条等高线包围的区域内，故通常只要使用外包的两条等高线的高程进行插值；DEM的表现形式—等高线用一组大小相同的网格描述地形表面；DEM的表现形式—Grid(2)规则网格(Grid)Grid把DEM表示成高程矩阵，DEM来源于直接规则矩形格网采样点或由不规则离散数据点内插产生;高程矩阵已成为DEM最通用的形式，特别有利于地形分析、绘制立体图等应用;缺点：地形简单地区存在大量冗余，如栅格过于粗略，不改变格网大小，则无法适用于起伏程度不同的地区；DEM的表现形式—Grid,ColoradoGrid地形表面

DEM的表现形式—Grid将分散的地形点按照一定规则(Delaunay规则)构成一系列不相交的三角形，以拟合地形表面。DEM的表现形式—TIN(3)不规则三角网(TIN)TIN可根据地形复杂程度来确定采样点的密度和位置，能充分表示地形特征点和线，减少地形平坦地区的数据冗余;DEM的表现形式—TIN高程数据地形因子：坡度、坡向、平面曲率、剖面曲率、地形起伏度、地表粗糙度、沟壑密度等；1.2.2基于DEM的信息提取定义：地表单元的法向量与Z轴的夹角，即切平面与水平面的夹角;在计算出各地表单元的坡度后，可对不同的坡度设定不同的灰度级，可得到坡度图;DEM的应用—信息提取

(1)坡度（slope）

(2)坡向（Aspect）地表单元的法向量在水平面上的投影与X轴之间的夹角在计算出每个地表单元的坡向后可制作坡向图，通常把坡向分为东、南、西、北、东北、西北、东南、西南8类，再加上平地，共9类，用不同的色彩显示，即可得到坡向图；DEM的应用—信息提取AspectDEM的应用—信息提取DEM的应用—信息提取(3)地表粗糙度（破碎度）~是反映地表的起伏变化和侵蚀程度的指标，一般定义为地表单元的曲面面积与其水平面上的投影面积之比，可以用地表单元顶点连接的对角线中点的高差表示地面粗糙度；DEM的应用—信息提取(4)高程变异分析包括平均高程、相对高程、高程标准差，高程变异；设地表单元格网4个顶点为pk（k=1，2，3，4），则高程平均值为若研究地区最低点高程为zmin，该地表单元的相对高程为高程变异是反映地表单元格网各顶点高程变化的指标，用格网单元顶点的标准差与平均高程的比值来表示：88.6%41.6%29.2%DEM的应用—信息提取（5）生成等值线等值线——表示具有相同高度、数量或浓度的连续的位置的集合。生成的等值线经过平滑处理，真实地再现表面等值线；三种方法：将DEM或Tin生成为线要素矢量主题；创建一个新的线主题，并从DEM主题或TIN中提取等值线，提取的等值线成为新主题中的要素;提取单条等值线；DEM的应用—等值线TUDEM的应用—等值线石河子市DEM及其等值线DEM的应用—等值线阴影可视性分析模拟飞行DEM的应用—可视化分析计算表面面积和体积三维景观显示1.2.3基于DEM的可视化分析DEM的应用—可视化分析给定太阳高度角、太阳方位角、光强度、光照时间，可增强地面起伏感，进行逼真的立体显示;（1）阴影—渲染光源来自西北产生正立体

光源来自东南产生反立体DEM的应用:可视化分析给定一个参考平面（指定高程），计算其上或以下的表面面积和体积；实际应用中一般用来计算土石方量（填、挖方）（2）计算表面面积和体积可交互式改变洪水的高度

计算水体积计算淹没表面积洪水淹没分析DEM的应用:可视化分析—表面面积和体积通过分析比较两个表面模型前后的变化，还可以计算填埋及挖掘土石方量；侵蚀沉积（3）填挖方分析DEM的应用:可视化分析—填挖方分析净增净减剖面分析常常以线代面，研究区域的地貌形态、轮廓形状、地势变化、地质构造、斜坡特征、地表切割强度等；如果在地形剖面上叠加其它地理变量，例如坡度、土壤、植被、土地利用现状等，可以提供土地利用规划、工程选线和选址等的决策依据；

（4）剖面分析DEM的应用:可视化分析准葛尔盆地-塔里木盆地-青藏高原DEM的应用:可视化分析—剖面分析DEM的应用:可视化分析—剖面分析已知两点的坐标A(x1，y1)，B(x2，y2)，则可求出两点连线与格网或三角网的交点，并内插交点上的高程以及各交点之间的距离。然后按选定的垂直比例尺和水平比例尺，按距离和高程绘出剖面图；DEM的应用:可视化分析—剖面分析剖面图绘制：剖面图不一定必须沿直线绘制，还可沿一条曲线绘制；剖面图绘制：DEM的应用:可视化分析—剖面分析（5）可视性分析实质上属于对地形进行最优化处理的范畴;例如：设置雷达站、电视台的发射站、道路选择、航海导航等、移动电话基站选址，在军事上如布设阵地（炮兵阵地、电子对抗阵地）、设置观察哨所、铺架通信线路等；分为：通视性分析和可视域分析DEM的应用—可视化分析通视性分析（Lineofsight）：通过此功能可显示两点之间的通视情况，从而判断从一个观察点是否可以看到目标物，回答了“从这里我可以看到哪个目标？”;可视域分析（Viewshed

Analysis）：确定从一个或多个观察点可以观测到的区域。回答了“从这里我可以看到什么？”的问题;DEM的应用—可视性分析通视分析是指以某一点为观察点，研究某一区域通视情况的地形分析。DEM的应用—可视化分析可视域分析可视域分析显示了在一个区域内从一个或多个观察点可以观察到的区域范围;在输出的Viewshed数据中，属性Value表示对于一个可视位置，有多少观察点可以看到此位置;DEM的应用—可视化分析观察点不通视通视雷达盲区飞行可视域的三维显示DEM+卫星影像三维地形景观DEM的应用—可视化分析

（6）三维景观表现杭州湾三维地形（7）模拟飞行DEM的应用—可视化分析DTM和DEM是数字形式的地形表面；DEM主要表现为Grid和TIN；DEM在现实中有着广泛应用。小结空间叠合分析：在相同空间坐标系统条件下，将同一地区两个或多个不同地理特征的空间和属性数据重叠相加，以产生空间区域的多重属性特征，或建立地理对象之间的空间对应关系；前提：同一地区、同一比例尺、同一数学基础(坐标系统和投影系统)、不同信息表达第二节空间叠合分析(Overlay)同一地区,同一比例尺,同一数学基础具有多重属性组合的新图层新属性

空间叠加的分类：按照数据结构，分为：矢量数据的叠加、栅格数据的叠加按照叠合对象图形特征，分为：点与多边形的叠合线与多边形的叠合多边形与多边形的叠合第二节空间叠合分析(Overlay)1.矢量数据叠加1.1点与多边形的叠加实质上是计算多边形对点的包含关系；1.矢量数据叠加1.1点与多边形的叠加生成的新图层仍然是点层；通过计算点与多边形的相对位置，判断点是否在多边形内，从而确定是否进行属性信息的叠加；叠加后生成一个新的属性表，该属性表不仅保留了原图层的属性，还含有落入的多边形的属性。例：1）查询：指定省有多少种矿产，产量有多少一个中国政区图(多边形)一个全国矿产分布图(点)叠加将政区图多边形有关属性信息加到矿产的属性数据表中属性查询2）查询：指定类型的矿产在哪些省份有分布A.点与多边形的叠加1.矢量数据叠加1.2线与多边形的叠加实质上是判断线段是否落在多边形内；生成一个新的线状数据层；1.矢量数据叠加1.2线与多边形的叠加通常是计算线与多边形的交点，只要相交，就产生一个结点，将原线打断成一条条弧段，并将原线和多边形的属性信息一起赋给新弧段；结果图层属性表包含原始线层和多边形的属性；可确定每条线段落在哪个多边形内,也可查询指定多边形内指定线段穿过的长度。例：线状图层：道路网可以得到每个多边形内的道路网密度多边形内部的交通流量进入、离开各个多边形的交通量相邻多边形之间的相互交通量与多边形叠加多边形将穿过它的所有道路打断成弧段线状图层：河流与多边形叠加多边形将穿过它的所有河流打断成弧段可以查询任意多边形内的河流长度计算它的河流密度线与多边形的叠加1.矢量数据叠加1.3多边形与多边形的叠加首先对多边形的边界进行几何求交，原始多边形被切割成新的弧段，再重建拓扑关系；1.矢量数据叠加1.3多边形与多边形的叠加生成新的多边形图层,综合输入图层的属性信息降雨量+土壤类型=适宜农作物1.矢量数据叠加1.3多边形与多边形的叠加叠合方式：unionintersectidentityeraseupdate1.矢量数据叠加1.3多边形与多边形的叠加叠合方式：union；1.矢量数据叠加1.3多边形与多边形的叠加叠合方式：intersect1.矢量数据叠加1.3多边形与多边形的叠加叠合方式：identityABCA+1.矢量数据叠加1.3多边形与多边形的叠加叠合方式：eraseABCA+1.矢量数据叠加1.3多边形与多边形的叠加叠合方式：update

ABCA+B实质：

图形和属性的布尔逻辑运算：并、交、差intersectunionerase1.矢量数据叠加2.栅格数据叠加前提:统一的栅格数据格式：BMP,JPEG,GRID等各个叠加层必须具有统一的地理空间，即具有统一的空间参考(包括地图投影、椭球体、基准面等)，统一的比例尺以及具有统一的分辨率(像元大小)。同一地区,同一比例尺,同一数学基础基本原理：地图代数通过对多层数据进行各种数学运算如加、减、乘、除、指数、对数等，或数学关系式（函数）计算，或统计值(最大值或最小值、平均值)等，建立多个数据层之间的关系模型；2.栅格数据叠加例：图层加法2.栅格数据叠加603369069693362022260466923820112302323112112212222233233420112302323112输入栅格输出栅格输入栅格×3＝×＝输出栅格乘数栅格2.栅格数据叠加例：图层乘法例：统计值——最大值2.栅格数据叠加2.栅格数据叠加例：统计值——最小值例：统计值——均值2.栅格数据叠加例：图层间函数关系

森林地区融雪经验模型：

M=(0.19T+0.17D)

M:融雪速度(厘米/天);T:空气温度;D:露点温度根据此方程，使用该地区的气温和露点温度分布图层，就能计算该地区融雪速率分布图；步骤：先分别把温度分布图乘以0.19和露点温度分布图乘以0.17，再把得到的结果相加；2.栅格数据叠加M=(0.19T+0.17D)要求：空气温度图层、露点温度图层的网格大小相同，坐标系统一致。××函数运算：两个以上层面的栅格数据系统以某种函数关系作为复合分析的依据进行逐网格运算应用：地学综合分析、环境质量评价、遥感数字图像处理等。土壤侵蚀多因子函数运算复合分析

利用土壤侵蚀通用方程式计算土壤侵蚀量降雨植被覆度坡度坡长土壤抗蚀性土壤侵蚀ArcView中，使用菜单mapcalculator（地图运算器）ArcGIS中，使用RasterCalculator（栅格运算器）案例：垃圾场选址要求：低渗透率Ca距市政区域保持一定距离Cb：>1km非环境敏感区Cc属农业区，非市政区或工业区Cd地表平均坡度平缓Ce：<2°不发生洪水（不属洪泛区）Cf根据条件组织相关图件；图层二值化：建立布尔逻辑条件，满足条件为Ture(=1)，不满足为Flase(=0)Output=CaANDCbANDCcAND

CdANDCeANDCf生成结果二值图：Ture(=1)为满足条件的合理位置；案例：垃圾场选址案例：中学选址现有中学的分布人口分布道路分布土地利用类型重点考虑因素：距离得分0—500米0（不必建设）500—1000米11000—1500米2>1500米3（必须建设）人口密度得分0-500（无需建设）50-1001100-2002200-3003（需要建设）

使用性质得分工业或绿地0（不能建设）商业1居住2（可以建设）中学的选址结果[R_land]×[R_popu]×[R_school]中学的选址结果[R_land]×[R_popu]×[R_school]使用性质得分工业或绿地0（不能建设）商业1居住2（可以建设）人口密度得分0-500（无需建设）50-1001100-2002200-3003（需要建设）距离得分0—500米0（不必建设）500—1000米11000—1500米2>1500米3（必须建设）[R_land][R_popu][R_school]邻近度（proximity)是定性描述空间目标距离关系的重要物理量之一；~表示地理空间中目标地物距离相近的程度，以距离关系为分析基础；第三节空间邻近度分析

2004年印尼海啸例银行网点的服务半径及其布局决策：新网点在哪设立？设立多少？例缓冲区分析定义、分类、生成、应用泰森多边形分析第三节空间邻近度分析

1.缓冲区分析缓冲区：为了识别某一地理实体或空间物体对其周围地物的影响度（影响范围或服务范围）而在其周围建立的具有一定宽度范围的带状区域（多边形）；1.1缓冲区分析的原理对一组或一类地物按缓冲的距离条件，建立缓冲区多边形，然后将这一图层与需要进行缓冲区分析的图层进行叠加分析，得到所需结果；缓冲区分析是GIS的基本空间操作功能之一，一般应用于求地理实体的影响范围；1.2缓冲区的分类根据数据格式：根据缓冲条件：根据对象影响力的特点：常数变量均质非均质矢量栅格（1）根据缓冲条件常数变量R=10R=10W（2）根据对象影响力的特点均质缓冲区：与邻近对象只呈现单一的距离关系，缓冲区内各点的影响度相等，不随与空间物体的距离远近而有所改变；如：军事管制区非均质缓冲区：空间物体对邻近对象的影响度随距离变化而呈不同强度的扩散或衰减；如：噪声传播非均质缓冲区：火箭发动机产生的噪声可能对周围环境产生的危害区域和危害程度

（2）根据对象影响力的特点非均质缓冲区：移动信号强度（2）根据对象影响力的特点1.3缓冲区建立方法1.3.1矢量数据缓冲区的建立方法点要素的缓冲区线要素的缓冲区面要素的缓冲区

（1）建立点要素的缓冲区以点要素为圆心，以缓冲距离R为半径做圆；R（2）建立线要素的缓冲区以线为轴线，以缓冲距离R为平移量向两侧作平行线，在轴线的两端构造两个半圆弧，最后形成圆头缓冲区；算法：角分线法凸角圆弧法(常用)

RRRRR★以面的边界线为轴线，以缓冲距离R为平移量向边界外侧或内侧作平行线所形成的多边形；RR（3）建立面要素的缓冲区1.3.2建立栅格数据的缓冲区像元加粗法:

计算栅格到周围栅格的距离，按照设定的缓冲距离R提取符合要求的栅格单元并与原图作布尔运算;2.82.22.02.22.82.21.41.01.42.22.01.001.02.02.21.41.01.42.22.82.22.02.22.8给定多个缓冲区距离，生成多个嵌套的缓冲区多边形：1.3.3多重缓冲区多个实体的缓冲区，为各实体缓冲区的并，半径可以不同；

栅格数据距离变换提取一定宽度的多边形缓冲区1.3.4多个实体的缓冲区1.4确定缓冲区半径的模型根据实体对周围实体的影响性质不同线性模型：实体影响度随距离的增大而呈线性衰减幂函数模型:实体影响度随距离增大而呈幂函数衰减指数模型：实体影响度随距离的增大而呈指数衰减Fi=f0(1-ri)Fi=f0(1-ri)2Fi=f0(1-ri)0.5050影响程度

Fi1.0100距离ri1.5缓冲区分析应用作为一个独立的数据层参加叠加分析:结合专业模型，为城市规划、景观生态、环境保护及污染治理、军事等提供科学依据；Whichparcelsarewithin50feetoftheroad?气象站点数据区域内所有点的数据2.泰森多边形分析泰森多边形：根据有限的采样点数据生成多个面区域,每个区域内只包含一个采样点，且各个面区域到其内采样点的距离小于任何到其他采样点的距离，则该区域内其他未知点的最佳值就由该区域内的采样点决定；2.泰森多边形分析将所有离散点连成三角形，作每个三角形各边的垂直平分线，各垂直平分线便围成一个多边形，用这个多边形内所包含的一个唯一点的值来表示整个多边形的值；2.1泰森多边形的构建生成泰森多边形的步骤由离散点构建Delaunay三角网；将各离散点相邻的所有三角形编号，并按顺或逆时针排列；作各三角形各边的垂直平分线，记录各三角形的外接圆圆心根据三角形顺序，连接所有外接圆圆心，生成泰森多边形；对于三角网边缘的泰森多边形，可作垂直平分线与图廓相交，与图廓一起构成泰森多边形；125432.2泰森多边形的特性每个多边形仅含有一个控制点数据;泰森多边形内的点到相应控制点的距离最近;位于泰森多边形边上的点到其两边控制点的距离相等若泰森多边形是n边形,则与n个离散点相邻。2.3泰森多边形的应用:根据离散点的影响力划分空间范围的情况，以及在缺少连续数据的情况下作近似替代，快速赋值(其中隐含假设是任何地点的未知数据均使用距它最近的采样点数据)；适合于专题数据的内插,可以生成专题与专题之间明显的边界；第四节网络分析(NetworkAnalysis)柯尼斯堡七桥问题找到一条路线，可以经过所有七座桥，但不重复经过任一座桥1.网络分析概述

网络是一个由点、线的二元关系构成的系统，常用来描述某种资源或物质在空间上的运动，形成各种物质、能量和信息流通的通道道路网,各类管网(水,电、气),流域水网各种服务网络（通信）……比例尺：1：3600日常生活、学习中的网络空间分析AB比例尺：1：1800300m380m415m400m石河子客运站到天扬超市的最佳路径1.网络分析概述

空间网络分析是GIS空间分析的重要组成部分数学定义：~以图论和运筹学为基础，通过研究网络的状态，模拟和分析资源在网络上的流动和分配情况，对网络结构及其资源等的优化问题进行研究；GIS定义：~依据网络的拓扑关系（线性实体之间、线性实体与结点之间，结点与结点之间的连接、连通关系），通过考察网络元素的空间及属性数据，以数学理论模型为基础，对网络的性能特征进行多方面的分析计算技术。1.网络分析概述

理论基础：图论和运筹学；解决两大类问题：一类是研究由线以及连接线的点组成的地理网络的结构，其中涉及优化路径的求解、连通分量求解等问题;另一类是研究资源在网络系统中的分配与流动,主要包括资源分配范围或服务范围的确定、最大流与最小费用流等问题；1.网络分析概述1.网络分析概述

网络的数据结构组成：几何结构：表示网络的地理分布位置，用矢量数据的点、线表达；拓扑结构：表示网络中各元素的连接关系，用图的形式表达；e5e2e1e3e4e6V4V1V2V32、网络的组成

网络:一系列不同性质的点及弧段组成的系统3人10人学校8路公车终点站6人路径站点中心拐点障碍点段5人8路公车始发站结点结点(1)结点:网络的端点，也是任意两条线段的交点，如公车始发站、终点站；(2)链弧：网络中流动的管线，是构成网络的骨架，也是资源或通信联络的通道，如街道。2.1网络要素的表示链弧号起结点终结点长度(km)正方向阻强(km/h)反方向阻强(km/h)资源需求量2024145.33555（-1:表示不通，如单行道）…425535结点号需求量453546-20结点号资源最大容量服务范围服务延迟数2410002000…………学校车站(3)站点(停靠点)：网络中物流的装、卸位置,直接在相应的结点上赋需求量属性，负为下卸，正为装载;(4)中心：具有一定容量，能集中或分发资源的结点所处的设施，如河网水库，商业中心、库房。状态属性包括：资源最大容量、服务范围和服务延迟数(在其它中心达到某个数量时才提供服务)。2.1网络要素的表示结点号从弧段至弧段角度时间阻强(s)34L2L1906034L1L11803034L2L3-90-1(不允许拐弯)34L1L300(无阻强)34L1L2L3停靠点(5)障碍：资源不能通过(有限制)的结点如河流闸门，路障等；(6)拐点：网络中物流方向发生改变的点，有控制方向的作用。如道路转弯；2.1网络要素的表示:(1)阻碍：资源在网络中运行的阻力，用时间、成本等衡量，与链的长度、方向、属性等有关；(2)资源需求量：沿网络链可收集或分配给一个中心的资源总量，如某条街所住的学生数；(3)资源容量：网络中心为弧段的需求能容纳或提供的资源总数量，如接收的学生总数；2.2网络的属性2.3图和网络的表示(1)邻接矩阵：1234515432123451543215432e1e6e5e4e3e2e7e8154325035759560608070(2)关联矩阵1235415432e1e6e5e4e3e2e7e8e1e6e5e4e3e2e7e82.3图和网络的表示3.网络分析功能路径分析：最优路径分析资源分配资源分配、定位选址在空间网络分析中，路径问题占有重要的位置。人们常想知道在地理空间网络的两指定结点间是否存在路径，如果有，则特别希望找出其中的最短路径；在运输网络中找出运输费用最小的路径；在通讯网络中找出两点间进行信息传递具有最大可靠性的路径等等；3.1路径分析(1)静态最佳路径：给定每条链上的属性(距离)，求最佳路径。从p1到p2共有n条路径，计算各路径权数之和，最小者为最佳路径;(2)最短路径或最低耗费路径

确定网络中从起点、终点和要经过的一系列特定的中间点、链，求最短或耗费最小的资源运移最佳路线，即阻力最小的路径;(3)动态最佳路径分析

实际中权数可能是变化的，可能临时产生一些障碍点，要动态计算最佳路径;3.1路径分析求两点间的权数最小路径，常用算法:Dijkstra设V0为起点,求V0到其余各顶点Vi的最短路径基本思路：V0—Vi最短路径经过Vj，则Vj是此路径终点的前一个顶点，欲确定V0—Vi最短路径，首先要找出V0—Vj最短路径：

PRED﹛Vj﹜表示从V0—Vi

最短路径中终点Vi的前一点；V5V0V4V3V2V11003051050206010(4)最短路径算法:Dijkstra★V0-V2的最短距离为10①初始化：已标定顶点：X﹛V0﹜未标定点:M﹛V1,V2,

V3,

V4,

V5﹜最短距离:DIS﹛0,∞,10,∞,30,100﹜PRED﹛V0,V0,V0,V0,V0,V0﹜V5V0V4V3V2V11003051050206010V0-V1的最短路径中，V1的前一点是V0最短路径：Dijkstra算法★②在M中V0到V2(10)距离最近，故：已标定顶点：X﹛V0，V2﹜未标定点:M﹛V1,

V3,

V4,

V5﹜最短距离:DIS﹛0,∞,10,60,30,100﹜PRED﹛V0,V0,V0,V2,V0,V0﹜V5V0V4V3V2V11003051050206010V0-V3的最短路径中，V3的前一点由V0变为V2考察增加V2后，是否会改变V0-Vi的最短距离：V0—V3：∞V0—V2—V3：60最短路径：Dijkstra算法★V5V0V4V3V2V11003051050206010③在M中V0到V4(30)距离最近，故：已标定顶点：X﹛V0,

V2,

V4﹜未标定点:M﹛V1,

V3,V5﹜最短距离:DIS﹛0,∞,10,50,30,90﹜PRED﹛V0,V0,V0,V4,V0,V4﹜考察增加V4后，是否会改变V0-V3的最短距离：V0—V2—V3：60V0—V4—V3：50V0-V3的最短路径中，V3的前一点由V2变为V4V0-V5的最短路径中，V5的前一点由V0变为V4考察增加V4后，是否会改变V0-V5的最短距离：V0—V5：100V0—V4—V5：90最短路径：Dijkstra算法★V5V0V4V3V2V11003051050206010④在M中V0到V3(50)距离最近，故：已标定顶点：X﹛V0,

V2,

V4,

V3﹜未标定点:M﹛V1,

V5﹜最短距离:DIS﹛0,∞,10,

50,30,60﹜PRED﹛V0,V0,V0,V4,V0,V3﹜考察增加V3后，是否会改变V0-Vi的最短距离：V0—V5：90V0-V4-V3-V5：60V0-V5的最短路径V0—V4—V3—V5中，V5的前一点由V4变为V3最短路径：Dijkstra算法★V5V0V4V3V2V1100305