资源描述：
《基于数据库中间件与gis实现的最短路径算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第31卷第13期计算机工程2005年7月Vol.31№13ComputerEngineeringJuly2005·软件技术与数据库·文章编号：1000—3428(2005)13—0078—03文献标识码：A中图分类号：TP311基于数据库中间件与GIS实现的最短路径算法1211倪凯，叶雷，鲁铭，张超(1.华东师范大学地理信息科学教育部重点实验室，上海200062;2.上海商学院连锁经营系，上海200255)摘要:地理信息系统中的空间网络分析有最短路径分析、资源分配分析、等时性分析等等,而最短路径分析是其中关键的环节,因而对其算法进行优化很有必要,为此在传统的最短路径算法,即Dikstra
2、算法的基础上,采用关系数据库的存储机制，实现对最短路径查询，不但降低了系统的开销，而且较好地解决空间数据访问的并发控制问题和数据安全性问题。通过具体案例分析表明,该方法是有效可行的。关键词：Dijkstra算法;最短路径;数据库中间件;地理信息系统ImplementationofShortestPathAlgorithmBasedonDatabaseMiddle-ware&GIS1211NIKai,YELei,LUMing,ZHANGChao(1.KeyLaboratoryofGeographicInformationScience,MinistryofEducation,ECNU,Sh
3、anghai200062;2.DepartmentofChain,ShanghaiBusinessSchool,Shanghai200255)【Abstract】InGIS,itisnecessarytooptimizetheanalysisfunctionoftheshortestpathasthehingeofspatialnetworkanalysis,whichincludesshortestpathanalysis,resourceallocationandisochrone,andsoon.Herederivedfromthetraditionalcalculatingmet
4、hod,ie.Dijkstraalgorithm,thequeryaboutshortestpathisbasedonrelationshipdatabase.Thistechniquenotonlysolvestheproblemofspatialdatasharingbutalsoimprovetheefficiencyofcomputersystem.【Keywords】Dijkstraalgorithm;Shortestpath;Databasemiddle-ware;GIS在空间信息分析中，网络分析是GIS核心功能之一。网抽象为图的结构。这就需要先对原始道路图进行处理，建立络分
5、析中最基本问题是最短路径问题，在交通网络分析系统其相应的网络拓扑关系。处理的工作主要包括:(1)对原始的中，它说明任意两个结点间的最短距离通路。从网络模型的道路图进行线元素的拓扑检查,生成线和线相互交叉的道路图;(2)对道路图创建拓扑关系，并定义其属性特征，如起始角度看，最短路径分析是指在指定网络中两结点之间找一条节点、终止节点、道路名称、道路距离等;(3)生成有拓扑关阻碍强度最小的路径，根据阻碍强度的不同定义，最短路径系的拓扑文件;(4)选取合适算法进行最短路径的计算。不仅仅指一般地理意义上的距离最短，还可以引申到其它的1.2最短路径的算法度量，如时间、费用、线路容量等。最短路径问题作
6、为许多关于最短路径的算法，目前所公认的最好的求解方法是领域中选择最优问题的基础，广泛应用于汽车导航系统以及1959年由E.W.Dijkstra提出的标号法。该方法之所以被称为各种应急系统等中，如110报警、119火警以及医疗救护系标号法，是因为这个方法在求解过程的每一个步骤中，都对统，特别是SARS传染疾病的出现，使地理信息系统中对最于网络图中的每一个顶点赋予一个或几个相应的数，这个数短路径的分析具有特别重要的意义。或这些数就称为该顶点的标号。这个算法的一个突出优点1最短路径问题是：它不仅可以求出起点致终点的最短路径及其长度，而且1.1何为最短路径可以求出起点到其它任何一个顶点的最短路径
7、及其长度。最优路径是基于数据结构中图的理论而产生，从数据结设G=(V,A)是一个赋权有向图，即对于图中的每一条边构的角度说，它是对图的一种搜索和权值的相加，此处的权e=(vi,vj)都赋予了一个权值wij。在图G中指定两个顶点，表示为从一个顶点到另一个顶点的距离或耗费。在地理网络确定为起点各终点，不妨设v1为起点vk为终点。标号法的中权可以代表多种不同的含义。如纯距离意义上的最短路基本思想是：首先从v1开始，给第1个顶点标一个数（称
