ArcGis Chapter02.doc

15

19
第二章 距离和时间的测量

本章介绍空间分析中经常遇到的一个问题：测量距离和时间。空间分析归根结底是考察自然和人类活动在空间分布上的变化，换言之，即考察这些活动相对于参照位置随距离的变化。很多时候，一旦通过GIS测定了距离或时间，我们就可以在GIS环境之外开展进一步的研究。GIS技术的不断进步和广泛应用使得相关研究工作变得越来越容易。
距离和时间的估算贯穿全书。例如，在第三章的空间平滑和空间插值中使用距离测量来确定纳入计算的对象及其对计算影响的程度。在第四章服务区分析中，商店与消费者之间的距离（或时间）确定了距离消费者最近的商店以及居民到商店购物的频率。第五章可达性测量中，距离或时间是构建移动搜寻法或引力法的基础。第六章考察的就是人口密度或土地利用强度从城市或区域中心向外随距离衰减的态势。在本书其他各章中也都会用到距离或时间的测量。
本章的结构如下。第2.1节概略介绍各种距离度量。第2.2节介绍如何计算网络的最短距离（时间）及其如何用ArcGIS来实现。第2.3节为方法示例，计算了中国东北地区各县与几大中心城市间的欧式距离和路网距离(Find/Replace all)。第2.4节是本章的简要小结。
2.1距离的测量
日常用到的距离包括欧式距离（直线距离）、曼哈顿距离和网络距离。欧式距离是两点之间的直线距离。除非特别说明，本章提到的距离都是欧式距离。
在有GIS之前，我们全靠用数学公式来计算距离，计算的准确性有限, 也受收集到的数据精度和所用和计算公式的复杂性影想。如果研究区的地理范围较小（如一个城市或一个县域单元），直角坐标系下两个结点(x1, y1) 、 (x2, y2)之间的欧式距离可以近似地表作
(2.1)

20
如果研究区范围较大（如一个州或一个国家），则需要计算大地距离,要考虑到地球的曲面。两点之间的大地距离是假设地球为球形时两点之间的最大圆弧的长度。已知两点的地理经纬度坐标以弧度计为(a, b)、(c, d)，他们之间的大地距离为
(2.2)
这里，r为地球半径（约为6,367.4 km）。
正如其名，曼哈顿距离是度量那些路网类似纽约曼哈顿区(正北正南直东直西)距离。曼哈顿距离是x和y方向距离之和。欧氏距离是直角三角形中的弦, 曼哈顿距离为勾,股之和。例如，直角坐标系下，两点(x1, y1)、 (x2, y2)之间的曼哈顿距离记为
(2.3)
与式（2.1）一样，式（2.3）定义的曼哈顿距离只在一个较小地区内（例如一个城市）才有意义。
网络距离是基于实际路网(如公路网，铁路网)的最短路径（或最短时间或最小成本）距离，将在第2.2节中详细讨论。如果是栅格形路网，可以用曼哈顿距离近似地代替网络距离。
在ArcGIS中，可以通过简单地点击(“measure”)工具来得到两点之间的欧式距离（或若干点之间的累计距离）。许多ArcGIS空间分析会顺带给出一些距离值。例如，第1.3节介绍的距离连接（空间连接法）给出了两个空间数据集合中不同物体之间的最短距离。在空间连接中，线或多边形之间的距离是最近点之间的距离。在ArcToolbox > Analysis Tools > Proximity中，Near工具用来计算图层中任一点与另一图层中跟它最近的线或点的距离。某些操作需要用到同一图层或不同图层中任意两点之间的距离即距离矩阵。ArcToolbox里的点距离（Point Distance）工具可以实现这个功能，调用办法为依次点击ArcToolbox > Analysis Tools > Proximity > Point Distance。在输出文件中，如果DISTANCE值为0，则可能实际距离确实为0（例如，某点跟它自身的距离），也可能是超出了搜索半径之外。
当前ArcGIS版本中没有内嵌不太常用的曼哈顿距离计算工具。计算曼哈顿距离时，需要从ArcToolbox生成各点的直角坐标。对于一个shape文件，可以调用Data Management Tools > Features > Add XY Coordinates来实现。对于一个coverage文件，可以调用Coverage Tools > Data Management > Tables > Add XY Coordinates来完成。在ArcGIS中计算网络距离则更为复杂，我们将用以下两节介绍。
21
2.2测算网络距离和网络时间
网络由一组结点及连接结点的线段（边或连接线）组成。如果线段方向是确定的（如单向的街道），我们得到一个定向网络。一个没有确定方向的网络可以看作定向网络的一种特例，即每条线段有两个可能的方向。最短路径问题就是寻找从某个起点到某个终点之间的最短路径，即在给定线段阻滞（如旅行速度）的情况下距离最短或时间（费用）最省。最短路径问题有多种解决办法，如本节将要讨论的标号设定算法及附录2中介绍的赋值图像法（或L-矩阵法）。
2.2.1最短路径问题的标号设定算法
广为使用的标号设定算法最早由迪卡斯缺（Dijkstra,1959）提出。该方法是这样的，为每个结点设置一个“标签”，代表到某个结点的最短距离。为简便起见，起始结点被名为结点1。本法包括如下四步：
1. 赋予起始结点（结点1）的固定标签y1=0，其他结点赋予一个临时标签yj=M（一个很大的数）。令i=1。
2. 以结点i为起点，重新计算临时标签yj=min（yj，yi+dij），从而得到结点j的临时标签，并且dij<M（dij是i、j之间的距离）。
3. 寻找所有临时标签中的最小值，例如yi。于是，结点i得到一个固定的标签值yi*。
4. 重复上述2～3步直到所有结点都得到一个固定的标签值。
我们用下面的例子来演示这种方法。图2.1a为由结点及连接线组成的网络，连接线上的数字为阻滞。
第（1）步，设置结点1的固定标签值为y1*=0；临时标签 y2 = y3 = y4 = y5 = M。令i=1。固定标签以“*”标记。见图2.1b。
第（2）步，结点1与结点2、3相连，于是重新计算得到2、3的临时标签。y2 = min (y2, y1+d12) = min (M, 0+25) = 25，类似地，y3 = min (y3, y1+d13) = min (M, 0+55) = 55。
第（3）步，最小的临时标签值是min (25, 55, M, M) = 25 = y2。于是给结点2一个固定标签，令i=2。见图2.1c。
22
回到第（2）步，重新计算结点3、4、5的临时标签值。结点2与结点3、4、5相连。y3 = min (y3, y2+d23) = min (55, 25+40) = 55, y4 = min (y4, y2+d24) = min (M, 25+45) = 70, y5 = min (y5, y2+d25) = min (M, 25+50) = 75。
再是第（3）步，最小临时标签值为min (55, 70, 75) = 55 = y3。给结点3一个固定标签，令i = 3。参见图2.1d。
再回到第（2）步，重新计算结点4、5的临时标签值。结点3与结点5相连，则y5 = min (y5, y3+d35) = min (75, 55+30) = 75。
再是第（3）步，最小临时标签值为min (70, 75) = 70 = y4。给结点4一个固定标签，令i = 4。参见图2.1e。
再回到第（2）步，计算结点5的值。从结点4到结点5，可得y5 = min (y5, y4+d45) = min (75, 70+35) = 75。
结点5是剩下的唯一临时标注点，因此我们给它一个固定标签。于是，所有结点都得到一个固定值，问题得到解决。参见图2.1f。
23
固定标签值yi是结点1到结点i之间的最短距离。一旦某个结点被赋予一个固定的标签值，则该结点被扫描一次。当标签改变时，最短距离随之改变，并以“扫描结点”的形式保存下来（Wu and Coppins, 1981: 319）。上面的例子可以总结为表2.1。
2.2.2用ArcGIS测算网络距离和时间
ArcGIS中处理的网络包括交通网络和市政管道网络，我们这里只讨论交通网络。许多GIS教科书（如Chang（2004），第十六章；Price（2004）第十四章）讨论了如何用ArcGIS获取两点之间的距离（或某点与多个点之间的距离）。在许多空间分析中，我们需要一系列起点和终点两两之间的距离矩阵。为此，需要用ArcInfo工作站，即用ArcPlot模块里面的NODEDISTANCE命令。默认情况下，NODEDISTANCE命令是通过公路网络来计算最短距离。同时它也提供了计算欧式距离或曼哈顿距离的选项。恰当地定义选项IMPEDANCE作为时间或成本，就可以计算最短交通时间或最小交通成本。下面介绍如何用ArcGIS计算网络距离矩阵。
第一步，建立网络。交通网络由线段费时、转弯费时、单行线、天桥、地下通道等网络要素构成（Chang, 2004: 351）。建立这样一个路网的数据采集和处理工作量都很大，往往是非常昂贵甚至是不可行的。例如，从美国人口普查局的TIGER线文件里提取的公路图层并不包含公路结点、转弯参数或限速等信息。在此情况下，我们只好假设用一些自动工具（如ArcGIS里构建拓扑关系的工具）生成的公路结点是相对可靠的，近似反映了真实路网的情况。而对于线段费时，我们可以基于道路等级设定限速标准，并考虑到交通堵塞的因素。有的研究（Luo and Wang, 2003根据美国统计局）在TIGER线文件中公路等的CFCC编码来设定公路限速。另一项研究（Wang, 2003基于土地利用强度（商业和居住密度）及其他一些因素建立回归模型来考虑交通堵塞程度从而预测行车速度。
第二步，用NETCOVER命令建立网络计算的路径系统。
第三步，定义始结点、末结点及阻力参数。可以用CENTERS、STOPS、NODES等来定义始末结点，用IMPEDANCE指定用网络属性表中的哪一项来定义线段长度或费时。
24
最后，用NODEDISTANCE命令来计算始末结点之间的网络距离。
需要注意的是，NODEDISTANCE命令只计算网络上结点之间的距离。但是，起始点或终点有可能并不在网络上。虽然起始点（或终点）到网络结点之间的距离有可能很小，但仍需计算在内。这是计算网络距离时需要考虑的一个重要步骤，详见下面的案例2。
2.3案例2：测算中国东北地区各县到四大中心城市之间的距离
本例计算中国东北地区各县到中心城市之间的距离。所得结果将在案例4B中用于定义城市腹地（参见第四章，第4.4节）。
我们的研究区选为中国的东北平原是因为该地区是一个相对完整的区域。包括三个省：黑龙江、吉林和辽宁。按人口和经济规模划分，有4大中心城市：三个省会城市（哈尔滨、长春、沈阳）和大连。铁路一直是中国客货运输的主要方式，在本研究区尤其如此，因此这里用铁路来测量网络距离。参见图2.2。
本书光盘提供了本例所需的下述数据：
1. 包含中国东北地区203个县（或县级行政单元）的多边形文件cntyne；
2. 本区4大中心城市的点文件city4；
3. 研究区铁路网络的线文件railne。
为了保证网络的完整性，铁路网络涵盖的范围比三个省区略大。这里关于各县和中心城市的空间数据是从中国县级单元GIS数据库中提取，可以从 http://sedac.ciesin.columbia.edu/china下载。铁路数据由中国科学院地理科学与资源研究所的金凤君先生提供。
2.3.1测算欧式距离和曼哈顿距离
如前所述，欧式距离和曼哈顿距离可以通过网络分析中心NODEDISTANCE命令来实现。本节介绍如何不用到网络分析来计算这两种距离。曼哈顿距离不适于象中国东北这么大区域范围内的测量（参见第2.1节），下面第（3）-（5）步中演示的曼哈顿距离的计算方法, 为可选操作。
1.生成县域重心
在ArcToolbox中依次选择Data Management Tools > Features > Feature To Point，选择cntyne作为输入要素，并将输出要素（县域重心）命名为CntyNEpt，选中选项。 “Inside”（既重心在县城范围）
2.计算欧式距离
25
在ArcToolbox中，依次选择Analysis Tools > Proximity > Point Distance，选择CntyNEpt作为输入要素（Input Features），选择city4 (point)作为近邻要素（Near Features），并将结果命名为Dist.dbf。这里不需要限定收索半径，因为我们需要计算所有的距离。所得表中一共有203（县）× 4（市）= 812条距离记录。在距离表中加入一列airdist，根据公式airdist=distance/1000计算，得到欧式距离的公里数（原图距离单位是米）。
26
3.可选操作：添加县域重心及城市重心的XY坐标
在ArcToolbox中，依次选择Data Management Tools > Features > Add XY Coordinates，选择CntyNEpt作为输入要素。在CntyNEpt的属性表中，所得结果保存在point-x和point-y两列中。此外，在ArcToolbox中，依次选择Coverage Tools > Data Management > Tables > Add XY Coordinates，选择city4作为输入文件。在属性表city4中，所得结果保存在x-coord和y-coord两列中。
4. 可选操作：将坐标连接到县和市的距离表
在ArcMap中，右键点击表Dist.dbf，依次选择Joins and Relates > Join，用CntyNEpt （源数据表）中的FID和Dist.dbf（目标表）中的INPUT_FID作为连接关键词将二表连接在一起。类似地，用City4属性表中的FID和新Dist.dbf表中的NEAR_FID作为连接关键词将二表连接在一起。
5. 可选操作：计算曼哈顿距离
打开新表Dist.dbf，添加一列Manhdist，按照公式Manhdist = abs(x-coord - point-x)/1000+abs(y-coord - point-y)/1000计算数值。所得曼哈顿距离的单位为公里，通常比欧式距离大。
2.3.2第二部分：测算交通路网距离
26
27
两地之间（这里是起始县城与目的地中心城市）的交通距离由三部分组成。图2.3给出了一个示例：（1）第一段（S1）是县城编号76到它最近的铁路结点171的直线距离；（2）第二段（S2）是铁路上两结点171和162之间铁路网络距离（途经165和163两个结点）；（3）第三段（S3）是中心城市编号4到它最近的铁路结点162的直线距离。在这里，S1和S3以直线距离近似地代替，S2为两结点之间的路网距离。换言之，从县城#76到城市#4，假设其通行路径为：先从县城#76到最近的结点171，然后通过铁路到结点162（途经结点165和163），最后到达中心城市#4。本节的主要工作即是寻找这些距离县城或城市最近的铁路结点，然后计算上述三段的距离，最后将其加总。
1.准备交通网络图层
在ArcToolbox中，依次点击Coverage Tools > Data Management > Topology > Build，在railne图层上创建线拓扑关系。重复此过程，创建点拓扑关系。理想状态下，结点应定义为实际的铁路站点。但我们没有这样的数据，这里假设ArecGIS拓扑工具产生的结点就是铁路站点。
2. 计算县城、城市与最近铁路结点之间的直线距离
在ArcToolbox中，依次选择Analysis Tools > Proximity > Near，并选择CntyNEpt作为输入要素，railne（结点）作为最近邻要素（Near Features）。在更新后的CntyNEpt 属性表中，NEAR_FID列为距离县城的最近结点，而列NEAR_DIST为它们之间的直线距离。用图层city4重复上述操作得到离中心城市最近的结点：以city4（点）为输入要素，railne（结点）为最近邻要素。在更新后的City4属性表中，列NEAR_FID为距离城市最近的铁路网络结点，另外的一列NEAR_DIST为它们之间的直线距离。这一步工作分别得到了县城和城市与其最近铁路结点之间的直线距离（图2.3中的S1和S3）。
3. 寻找起，始结点对
在计算路网距离时，起(始)结点不能重复。在CntyNEpt属性表中，有多个县城对应NEAR_FID中的同一个结点。例如，编码FID = 5 及FID = 8的两个县城，其最近邻结点都是NEAR_FID = 34的结点。也就是说，一些近邻的县城共享铁路网络上的同一个最近邻结点（始结点）。在city4属性表中，每个中心城市对应不同的铁路结点（末结点），因此无需再处理, 四个中心城市对应于四个不同的末结点，下面介绍如何定义不重复的始结点。
打开属性表CntyNEpt，右键单击列NEAR_FID，选择Summarize，将结果保存为表Sum_FID.dbf，在该表中，列Cnt_NEAR_F（频率统计）代表每个NEAR_FID结点对应的县城数。当频率数大于1时，表明是多个县城共享同一个结点。表Sum_FID.dbf有149条记录，表明有149个不同的始结点。
4. 定义始末结点的INFO文件
28
这一步主要为下一步准备两个INFO文件：一个包括所有的始结点，另一个包括所有的末结点。这两个INFO文件都必须用ArcInfo workstation来生成。数据表Sum_FID.dbf用于生成始结点的INFO文件，属性表city4.pat本身已经是INFO文件了，它将用于生成末结点的INFO文件。在ArcInfo workstation中，多边形或点图层的属性表文件扩展名为.PAT，意为Polygon（Point）Attrabute Table多边形（或点）属性表；线（Arc）属性表文件的扩展名为.AAT；结点（Node）的属性表文件扩展名为.NAT。ArcInfo workstation里的操作方法如下：
在ArcInfo workstation中，切换到目标工程文件夹（路径）（例如，通过输入命令w c:\Quant_GIS\proj2来实现），然后输入下述命令（这里，“/*” 之后的内容为命令行的注释说明）:
Dbaseinfo sum_fid.dbf tmp /* sum-fid。dbf转换成名为“tmp”的INFO文件
Pullitems tmp fm_node near_fid /* 提取tmp中的“near_fid”，并生成INFO文件“fm_node”，即始结点文件
Pullitems city4.pat to_node near_fid /*提取city4.pat中的“near_fid”并生成INFO文件“to_node”，即末结点文件。
INFO文件fm_node和to_node中的列名称near_fid需要改为railne-id以便与铁路图层中的名字相对应。结点属性表railne.nat中的railne-id为每个结点的唯一标志码。这可以用ArcCatalog来实现：右键单击fm_node（或to_node），从内容菜单中选择属性（Properties），选择Items 标签，打开对话框窗口，点击Edit可以修改某项的名字。熟练的ArcInfo workstation用户，可以在workstation环境下修改变量名，也可以通过编写一段AML程序来自动实现。
5. 计算铁路网络结点之间的距离。
可以用下述ArcInfo workstation命令来实现：
ap /* 调用arcplot模块
netcover railne railroute /* 设置路径系统
centers fm_node /* 定义始结点
stops to_node /* 定义末结点
nodedistance centers stops rdist 3000000 network ids
q /* 退出
在这里的“nodedistance”命令以3,000公里（或一个非常大的距离值）作为阈值，计算centers中每个结点跟stops中每个结点两两之间的距离，所得结果生成一个名为rdist的INFO 文件。最后两个参数是可选参数：“network”为默认选项（其他两个选项为“Euclidean”、“Manhattan”，分别用于计算欧式距离和曼哈顿距离），参数“ids”用于指定结点的ids值作为始末结点的唯一标志（默认值为“noids”）。在INFO文件rdist中，railne-ida项用于确定始结点，railne-idb项用于确定末结点，而network是它们之间的距离。上述过程用于计算始末结点之间的距离（即图2.3中的S2）。在fm_node表中有149个始结点，表to_node中有4个末结点，从而rdist中有149×4 = 596条距离值，这比欧式距离文件Dist.dbf中的812条距离值要少。
29
下一步是将这三段距离值连接到一起：S2保存在表rdist中，而我们在上述第2步中得到的S1和S3分别保存在更新后的表CntyNEpt和city4中。然而，我们不能简单地将CntyNEpt和rdist连接起来得到S1和S2。由于每个末结点对应唯一的中心城市，把表City4和rdist连接起来（基于共同的末结点），从而得到一个包含距离S3和S2的表是不存在问题的。在上面第3步中我们已经提到，每个始结点可能对应着CntyNEpt中的若干个县城；而一个始结点又对应着rdist 中的4个末结点。因此，表CntyNEpt和rdist的关系将会是多对多的关系，这给我们创建包含S1、S2、S3这三段距离值的数据表带来一个挑战。在下面第6步中，我们将用欧式距离文件Dist.dbf作为一个模板来实现这个任务。图2.4(a)-(c)为这一过程的示例，可以方便读者理解。
6. 添加直线距离值
在ArcMap中，右键点击欧式距离表Dist.dbf，依次选择Joins and Relates > Remove Join(s)。这是为了去掉前面操作时连接的一些不必要的数据列。与第一部分中的第4步类似，两次使用“join”：将属性表CntyNEpt连接到表Dist.dbf（对应的连接标志分别为FID和INPUT_FID），将属性表city4也连接到Dist.dbf（对应的连接标志分别为：FID和NEAR_FID）。注意到属性表得到了更新，即上述第2步计算得到的直线距离值S1和S3添加到了表Dist.dbf中：CntyNEpt.NEAR_DIST为县城与最近邻结点之间的距离， point:NEAR_DIST为中心城市与其最近邻结点之间的距离。图2.4(a)为本步的图示。
7. 添加路网距离值
为了将路网距离值rdist连接到表Dist.dbf，我们需要创建一个公共的连接标志linkid用于确定始末结点的唯一铁路路径。列linkid 由始末结点的ID标志组成。
打开INFO表rdist，添加一列linkid（定义类型为“long integer”）并根据公式linkid = 1000*railne-ida + railne-idb计算。例如，如果railne-ida = 198，railne-idb = 414，则linkid = 198414。参见图2.4(b)中的左表。类似地，在表Dist.dbf中添加列linkid并根据公式Dist.linkid = 1000*CntyNEpt.NEAR_FID+point:NEAR_FID计算。参见图2.4(b)中的右表。最后，基于公共标志linkid将rdist连接到表Dist.dbf。
8. 汇总三段距离值
31
在Dist.dbf中新增一列RoadDist（定义其类型为“float”），根据公式Dist.RoadDist = (CntyNEpt.NEAR_DIST + point:NEAR_DIST + rdist:network) /1000计算数值。这里，表Dist.dbf中的RoadDist为各县城与各大城市之间的交通网络距离（公里）。图2.4(c)为最后的结果。
2.3.3第三部分：测算交通时间
第二部分演示了测算路网距离的方法。测算交通时间的方法与此类似，下面仅仅指出二者的不同之处。
在第1步中，在路网属性表railne.aat中添加速度属性speed，并为每段道路赋予一定的速度。然后，在该表中添加一列时间属性time，并根据公式time = length/speed计算。注意距离和速度的单位，必要时进行单位换算。例如，如果速度为km/hr，则公式应为time = (length/1000)/speed，所得时间的单位是小时。
在第5步中，在执行NODEDISTANCE命令之前，添加一条命令用于定义交通阻力项：impedance time。在INFO文件rdist中，属性项network代表时间而不是距离。
在第8步中，可以为两端的直线距离赋予一个假设的速度值。假设速度为50 km/hr，则全程的时间（小时）计算公式为：Dist.roadtime = (CntyNEpt.NEAR_DIST + point:NEAR_DIST) /1000/50 + rdist:network。
最后，我们可以用ArcCatalog删掉一些不需要的数据，只要在表Dist.dbf中保留所有的距离值（每条记录包含三段距离）即可。这里的距离值将用于案例4B。
2.4小结
本章主要介绍了四种基本的分析技巧：
（1）测算欧式距离；
（2）测算曼哈顿距离；
（3）测算网络距离；
（4）测算交通时间。
欧式距离和曼哈顿距离很容易通过GIS来得到，而计算网络距离和交通时间需要道路网络数据，计算步骤要复杂一些。本书后面一些章节中还会涉及欧式距离、网络距离或交通时间的计算，本章学到的这些基本技巧还有更多的训练机会。

附录2 用赋值图法求解最短路径问题
赋值图或L矩阵提供了另外一种求解最短路径的方法（Taaffe et al, 1996: 272-275）。
32
以图A2.1所示的网络为例。这个网络代表了俄亥俄州北部地区的高速公路网，结点1为托莱多（Toledo），结点2为克里夫兰（Cleveland），结点3为剑桥（Cambridge），结点4为哥伦布（Columbus），结点5为代顿（Dayton）。我们用一个L1矩阵来表示这个网络，矩阵的每个元素为两结点之间的直接距离（一步直接相连）。如果两个结点之间没有直接的交通联络，则用一个很大的数M表示。对角线上的元素L1(i, i)都为0，因为结点与自身的距离为0.
接下来，我们用矩阵L2代表2步连接。在L1矩阵中那些非M值的元素保持不变，因为二步连接不可能比一步连接（直接连接）还要短。我们只要修改那些M值即可。例如，L1(1, 3) = M需要修改，下面列出了所有可能的“二步”连接：

L1(1, 1) + L1(1, 3) = 0 + M = M ;
L1(1, 2) + L1(2, 3) = 116 + 113 = 229 ;
L1(1, 3) + L1(3, 3) = M + 0 = M ;
L1(1, 4) + L1(4, 3) = M + 76 = M ;
L1(1, 5) + L1(5, 3) = 155 + M = M .
元素L2(1, 3)的值为上述连接的最小值，即L1(1, 2) + L1(2, 3) = 229。值得注意到是，它不仅记录了结点1、3之间的最短距离，也记录了二者之间的通行路径（途经结点2）。
类似地，我们可以得到其他元素的值，有L2(1, 4) = L1(1, 5) + L1(5, 4) = 155 + 77 = 232, L2(2, 5) = L1(2, 4) + L1(4, 5) = 142 + 77 = 219, L2(3, 5) = L1(3, 4) + L1(4, 5) = 76 + 77 = 153，等等。矩阵L2的最终结果见图A2.1。
现在，矩阵L2中所有元素都有一个确定的值，所有M都已经被替换，从而我们得到了最短路径问题的解。如果矩阵L2仍然有待定的M值，则我们需要继续进行矩阵运算，直到所有的M值都被确定的数值替换。例如，L3 可以这样计算：

表 2.1 求解最短路径问题

始末结点
路径包含的曲线段
最短距离
1, 2
(1, 2)
25
1, 3
(1, 3)
55
1, 4
(1, 2), (2, 4)
70
1, 5
(1, 2), (2, 5)
75