在ArcGIS矢量图中搜寻最短路径的实现

1、16北京测绘年第期在ArcGIS矢量图中搜寻最短路径的实现高吉（北京林业大学，北京100083）摘要最短路径问题是地理网络分析中的重要问题之一，具有重要的应用价值。搜索最短路径的方法很多，在研究了各种方法后，本文提出了在ArcGIS矢量图中搜索最短路径的新方法。首先，提取经过ArcGIS简单用MATLAB建模来提取节点间的最短路径，最后根据模型运算的处理的矢量图的信息，然后，借助Floyd算法，结果在矢量图中绘出最短路径。试验证明，该方法操作简单，效果良好。关键词最短路径算法；地理信息系统；MATLAB中图分类号P208文献标识码B文章编号1007-3000（2009）02-3随着对地观测和计

2、算机技术的发展，空间信息及处理能力已极大丰富和加强了，人们渴望利其分析、用这些空间信息来认识和把握地球和社会的空间运动规律，进行虚拟、科学预测和调控，而空间分析也很人们运用空间分好的满足了用户这样的需求。例如，析中的网络分析技术可以很好的完成资源的最佳分配、最短路径的寻找、地址的查询匹配1这样的任务。其中的最短路径分析成为当前研究的热点。“最短路也即最佳路径，它包括很多含义，最短路径不仅仅径”指一般地理意义上的距离最短，还可以引申到其他的度量，如时间、费用、线路容量等2。ArcGIS软件自带的网络分析模块有分析矢量数据的功能，但只对具有拓扑关系的矢量数据进行分析，在进行网络分析之前，必须对交通

3、矢量数据进行拓扑然后利用ArcGIS网络分析工具建立几何网络并分析。进行最佳路径分析。这种方法较为繁琐，不好掌握。为方便最短路径的提取，本文通过直接对矢量图进行简单的处理，导出点和线的信息，利用MATLAB建模采用先进的Floyd算法进行最短路径的分析。MATLAB是以复数矩阵作为基本编程单元的一种程序设计语言，它提供了各种矩阵的运算和操作，并具有较强的绘图功能3。最短路径问题中有许多需要进行矩阵运算的算法，用C语言之类的高级语言来实现这类算法就比较繁琐，编程起来也特别复杂，即使是一个矩阵求逆也需要很长一段程序来实现，而MATLAB中则给出了许多进行矩阵运算的高效的函数，使用起来很方便。1最短

4、路径及其算法图论中对最短路径的定义为：设带权图GV,E,W，G中每条边带的权均大于等于0，u、v为G中任意两个定点，从u到v的带权最小的通路称为u到v的最短路径4。最短路径包括单源最短路径和任意节点间的最短路径。单源最短路径为：从某结点s到其它所有结点的最短路径；任意节点间的最短路径为：对每一对已知一个各边权值均大于0的带权有向图，顶点（Vi，V）要求求出Vi与Vj之间的最短路径和最j，短路径长度。求解最短路径的经典算法为E.W.Djstra于1959年提出的标号法，也称Djstra算法5-6。其常规办法是：轮流以每一个顶点为源点，重复执行Dijkstra算法n次，就可求得每一对顶点之间的最短

5、路径以及最短路径长度。但是还有比对图中每个顶点重复进行一次Dijkstra算法更有效的算法，就是由弗洛依德提出的Floyd算法7，也称插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。Floyd算法的计算思路为：从图的带权邻接矩阵G开始，递归地进行n次更新，即由矩阵D(0)=G，按一又用同样地公式由D(1)构个公式，构造出矩阵D(1)；造出D(2)；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是顶点i到顶点j的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。22.12.1.1搜寻最短路径在ArcGI

6、S中实现矢量图的信息提取矢量图预处理首先对矢量图中的线图层进行处理，完善线图层的长度、端点、名称等信息。接下来对矢量图进行交集高吉)男，河南鹤壁人，GIS。年第期北京测绘17（intersect）操作，得到线路的交点，然后为这些交点建立点图层并编号。最后生成如图1所示的线路。假如D(5,1)=3则说明从V5到V1经过V3，路径据D，为V5,V3,V1，如果D(5,3)=3，说明V5与V3直接相连。下面为用MATLAB语言编写的Fold算法程序：functionD,path=floyd(G)n=size(G,1);D=G;path=zeros(n,n);fori=1:nforj=1:n图1线路图

7、ifD(i,j)=infpath(i,j)=j;endendendfork=1:nfori=1:nforj=1:nifD(i,k)+D(k,j)4-7-8。2.1.2从图中提取线路和交点的信息分别从点和线图层中提取点和线的信息，然后保存文件的结构如下：到两个文本文件Line.txt和Point.txt中，Line.txt端点1编号，端点2编号，线路长度Point.txtX坐标，Y坐标，点号生成这两个文件后，用MATLAB建模读取它们的信息生成距离矩阵进行最短距离搜索。2.22.2.1在MATLAB中建模搜索最短路径读取点和线文件并建立图的邻接矩阵从点和线文件中提取结点和弧段的信息，建立图的邻接

8、矩阵G如下：G=inf2044.861898.311850.78infinfinfinf;2044.86infinf1828.241682.88infinfinf;1898.31infinf1755.85inf1821.66infinf;1850.781828.241755.85infinf1874.791725.47inf;inf1682.88infinfinfinf1688.282883.02;infinf1821.661874.79infinfinf2529.24;infinfinf1725.471588.28infinf1497.76;infinfinfinf2883.022529.2

9、41497.76inf;其中G(i.j)表示点i到点j的距离，如果值为inf则表示两点间无线路。2.2.2用Floyd算法编程提取最短路径Floyd的算法过程为：a.把图用邻接距阵G表示出来，如果从Vi到Vj有路可达，则Gi,j=d，d表示该路的长度；否则Gi,j=空值。令D=G。b.定义一个矩阵path用来记录所插入点的信息，pathi,j表示从Vi到Vj需要经过的点，初始化pathi,j=j。c.把各个顶点插入图中，比较插点后的距离与原来的距离，Di,j=min(Di,j,Di,k+Dk,j)，如果Di,则pathi,j=k。j的值变小，d.从D中提取两点之间最短路径的长度，从path3图

10、2结果结语最短路径问题是地理信息系统网络分析中最基本、最关键的问题，在交通网络结构的分析、交通运输线路的选择、通讯线路的建造与维护、运输货流的最城市公共交通网络的规划等方面都有重小成本分析、要的应用价值。本文通过直接对矢量图进行简单的处理，导出点和线的信息，利用MATLAB建模采用先进的Floyd算法进行最短路径的分析，对在ArcGIS中搜索最短路径进行了有益的尝试。本文给出18北京测绘年第期武汉测绘科技大学学报，1999，24(3)：209212方便，便于分析人员的操作，缺点是需要用到不同的软件，没有对这些功能模块进行集成，不利于集成处理。集成这些模块的最好方法是用ArcGIS支持的pyth

11、on语言建立最短路径分析模块，在ArcGIS软件内部调用这个模块提取最短路径，这也是本文研究的下一个方向。3王沫然MATLAB与科学计算机M北京：北京电子与工业出版社，200445耿素云，屈婉玲，张立昂离散数学M，第二版北京：清华大学出版社，1999：158ThomasHCormen，CharlesELeiserson，RonaldLRivest，andCliffordSteinIntroductiontoAlgorithmsMITPress，Cambridge，MA,20016卢开澄，卢华明图论及其应用M，第二版北京：清华大学出版社，19977美约翰森堡，谢菲尔大学算法教程M北京：清华大学出

12、版社，2007参考文献1汤国安，杨昕ArcGIS地理信息系统空间分析实验教程M北京：科学出版社，2006：192乐阳，龚健雅Dijkstra最短路径算法的一种高效率实现JImplementationofSearchingShortestPathinArcGISVectorGraphGAOJi(BeijingForestryUniversity,Beijing100083)Abstract:Asanimportantpartamongtheanalysisofgeographynetwork,theshortestpathanalysisvalue.Therearemanymethodsforf

13、indingtheshortestpath.Afterstudyingthem,thispapergivesashortestpathinArcGIsvectorgraph.First,distillinformationfromvectorgraphwhichhasbeenoperatedtheshortestpathbetweennodesbyusingMATLABtobuildamodelwhichactualizeFloydarithmetic.shortestpathinvectorgraphbasedontheresultoperatedbythemodel.Keywords:th

14、eshortestpatharithmetic；geographyinformationsystem；MATLAB（上接第68页）hasgreatapplicationnewwaytofindthebyArcGIS.Then,getIntheend,drawthe并利用空间叠加的方法，完成了4036个控制点高程转换更新。(3)到2007年底，利用“电子档案质量检查软件”检查了14554幅(块)图纸的扫描和14210幅(块)图纸的数据加工、数据处理的元数据采集和检审。4.2仍然存在的问题尽管我院在电子档案质量方面取得了一定的进展，但是仍然存在以下问题：(1)电子档案质量意识急待加强。长期以来，由

15、于只注重纸质档案，而且因为城市测绘档案实行双套制归档，在收入偏低的背景下对电子档案实施严格质量监控将增加档案工作量，个别人甚至认为加强电子档案质量“多管闲事”，这将直接妨碍质量意识的加强。管理是(2)检查电子档案质量的流程有待完善。现有的电子档案工作流程在质量监管中存在漏洞，主要包这括：电子档案制作的成果没有实现网络化流转，一方面导致工作状态无法进行监管状态，另一方面也使得容易出现电子档案成果出现错漏现象；电子档案的质量管理缺乏严格的电子签署或手工签署，从而使得档案工作人员无法感受到质量检查的重要性。(3)电子档案质量应进一步与奖惩挂钩。由于各种原因，档案工作人员的收入一直较低，更没有与质量和

16、奖惩挂钩，从而导致个别人员对电子档案质量重视不够，电子档案加工以完成任务和应付为目标，严重者甚至对电子档案质量事故置若罔闻。这急需得到解决。参考文献1肖建华，罗名海加强勘测电子档案管理、提高信息安全和利用水平M.城市勘测，2006，4:4-72李黎.城市勘测电子档案管理新方法M.档案学通讯，2007，增刊:107-1083罗名海，李黎等.城市勘测电子档案管理方法研究的总体思路M.湖北档案，2005，增刊：1294李黎，冯平等.城市勘测档案现状及发展M.中国档案，2007，8期专刊：122-1235李黎，李剑.基础测绘成果集成建设探讨M.江西测绘，2006，2：9-11GlancetheElec

17、tronicalArchivesQualityofCitySurveyingLILi1，HUANGYan，LIjian2(1.WuhanInstitute，No.209，WansongyuanRoad，Wuhan，Hubei，430022，China；2.GuangdongProvinceHighwayConstructionCompany，No.111，SiyouxinmaRoad，Guangzhou，Guangdong，516000，China)Abstract:Accordingtotheprofessionalcharacteristicsofthecitysurveying,wehadregulatedtheworkflowofitsa