dijkstra算法在gis中的优化实现-read

《dijkstra算法在gis中的优化实现-read》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、维普资讯http://www.cqvip.com计算机与现代化2005年第9期JISu删IYUXIANDAIHUA总第121期文章编号：1006-2475(21305)09．0019．02Dijkstra算法在GIS中的优化实现朱静(中国地质大学计算机系，湖北武汉430074)摘要：地理信息系~(GIS)的应用经常涉及最短路径搜索问题。1959年迪杰斯特拉(Dijkstra)提出的Dijkstra算法是最适合网络拓扑中两结点间最短路径搜索的算法之一。本文讨论一般公路交通网络中两结点问的最短路径搜索问题，从核心算法方面对Dijkstra算法进行改进。关键词：GI

2、S；Dijkstra算法；最短路径中图分类号：TP301文献标识码：AEfficientImplementationofUijkstraAlgorithminGISZHUJing(ComputerDepartment，ChinaUnivemityofGeoscienees，Wul~m430074，China)~：Theimplementationofgeographicinformationsystem(GIS)oftenc0rKmswithseekingshortestpath．DijkstraritIlmpre·~ntedbyDijkstrain1959i

3、soneofthemostsuitablealgorithmsforfindingtheshortestpathbetweentwonodesofgraphic．Thispaperdis·cussestheproblemthathowtolocatetheshortestpathbetweentwonodesin130111111011trl~cgraphic．andpresentsthemethodofraisingettleieneyofDijkstraalgorithm．Keywords：GIS；Dijkstraalgorithm；shortestpat

4、h1Dijkstra算法的优化途径2直线优化Dijkstra算法Dijkstra算法将网络结点分为未标记结点、临时Dijkstm算法一种行之有效的优化方法是：减小标记结点和永久标记结点3种类型。网络中所有结算法中成功搜索的搜索范围，以尽快到达目标结点。点首先初始化为未标记结点，在搜索过程中和最短其核心思想是：在所研究的网络可以被看成平面网路径结点相连通的结点为临时标记结点，每一次循络的条件下，将临时标记结点到源点的最短路径与环都是从临时标记结点中搜索距源点路径长度最短本临时标记结点到目标结点的直线距离之和作为此的结点作为永久标记结点，直至找到目标结点或者临时标

5、记结点的一个属性值，这个属性值将作为从所有结点都成为永久标记结点才结束算法。在原始临时标记结点集合中选取永久标记结点的依据，即选Dijkstra算法中，临时标记结点无序地存储在无序表取此属性值最小的临时结点作为永久标记结点，这中，这无疑成为Dijkstra算法的瓶颈，因为每次在临种优化方法称为直线优化Dijkstra算法。此方法使得时标记点中搜索路径最短的结点时，都要遍历所有的Dijkstm算法的搜索方向智能地趋向于目标结点，减临时标记结点。解决的办法就是将临时标记结点按少了算法中遍历的结点个数，从而提高了搜索速度。照最短路径排序，每个搜索过程不必全部遍历或者

6、直线优化nijkstra算法与原始Dijkstra算法的搜只较少地遍历临时标记点，这也是目前各种基于原索过程比较示意如图1所示。始Dijkstm算法的各种优化算法的重要出发点之一；原始Dijkstra算法的搜索过程，可近似为以源点另外一个优化途径是尽量减少最短路径分析过程中为圆心的一系列同心圆(如图1(a))，搜索过程没有搜索的临时结点数量，从而尽快到达目标结点。考虑终点所在的方向或位置，在从源点出发的搜索收稿日期：2004-11-16作者简介：朱静(1974-)，女(土家族)，湖北鹤峰人，中国地质大学(武汉)计算机系讲师，硕士，研究方向：地理信息系统。维普资

7、讯http://www.cqvip.com20计算机与现代化2O05年第9期过程中，其他结点与终点被搜索到的概率相同；直线最大搜索范围得到了明显的减小，从而使搜索速度优化Dijkstm算法的搜索过程，可近似为以源点和终得到提高，图3显示了两种算法的最大搜索范围。图点为焦点的一系列同心椭圆(如图l(b))。中圆为原始Dijkstm算法的最大搜索范围，椭圆为直线优化Dijkstm算法的最大搜索范围。直线优化Di—jkstra算法最大搜索范围与源点在网络中的位置有关。当源点接近网络边界或者处在搜索范围的网络边界上时，其搜索的结点数目可能会明显地少于原始Dijkstr

8、a算法的。表1两种l~kstra算法中