运筹学资料
快速Dijkstra最短路径优化算法的实现
司连法1,王文静2
(1.中国地图出版社,北京100054;2.武汉大学,湖北武汉430079)
RealizationofOptimalAlgorithmforFastDijkstraLatestPath
SILian-fa,WANGWen-jing
摘要:在分析已有Dijkstra算法的基础上,提出快速Dijkstra最短路径优化算法。该算法是将提高时间效率放在第一位,以十字链
表结构记录顶点(Vertex)和边(Edge)为基础,采用顶点分区和记录绝对地址来优化Dijkstra算法的方法。
关键词:最短路径;优化Dijkstra算法;GIS;
一、最短路径与Dijkstra算法
随着计算机和地理信息科学的发展,(地理GIS信息系统)的应用领域越来越广。最短路径问题作为地理学中一个重要问题,其在GIS中的应用无疑占有重要的地位,无论是交通运输,还是城市规划、物流管理、网络通讯等方面,它都发挥了重要的作用。因此,对它的研究不但具有重要的理论价值,而且具有重要的应用价值。
研究最短路径问题通常将它们抽象为图论意义下的网络问题,问题的核心就变成了网络图中的最短路径问题。当然,此时的最短路径不单指“纯距离”意义上的最短路径,它可以是“经济距离”意义上的最短路径,“时间”意义上的最短路径,“网络”意义上的最短路径。
关于最短路径问题,目前所公认的最好的求解也方法,是1959年由E.W.Dijkstra提出的标号法,就是人们常说的以他的名字命名的Dijkstra算法。在此算法思想基础上,人们演绎出了几十种不同的优化算法,效果较好的算法有TQQ(graphgrowth,(theDijkstra'salgorithmim-withtwoqueues)DKA,(theDi-DKDplementedwithapproximatebuckets)
jkstra'salgorithmimplementedwithdoublebuck-[1][2]
,排序优化算法等,前面3种算法将空间存ets)
顶点(Vertex)和边(Edge)为基础,采用顶点分区和记录绝对地址来优化Dijkstra算法的方法。
(V,是一个赋权有向图,即对于图中设G=E)的每一条边e=(vi,vj)都赋予了一个权值wij,表示点v1和vj之间的最短距离。在图G中(vj)D
指定一个顶点,确定为起点,不妨设v1为起点。
Dijkstra算法的基本思想是:
先给v1标上红色标号,且D(v1)1.开始,=0,(j≠1),红点是不可改变D其余各点D(vj)=+∞值的点,它所具有的D值即为该点至起始点的最短距离;
将从该点2.如果刚刚得到红色标号的点是vi,
进行扩展蓝点集,那么,对于所有这样的点{vj(|vi,,将其D(vj)而且vj的标号不是红色标号}vj)∈E,修改为:[D(vj),(vi)+wij],并将vj标上蓝minD色标号,蓝点是具有至起始点临时最短距离的点;
(vi)3.从所有标有蓝色标号的顶点中求得D最小的顶点vi,并将其标上红色标号,转向第2步,如果此步没有发现标有蓝点标号的顶点,则停止。
二、现有优化算法分析
TQQ,DKA,DKD算法是以节约存储空间为基础的算法,从当前计算机硬件发展水平来看,它们已经失去了优化的意义。本文只针对节约时间的优化算法作分析。
排序优化算法是一种较好的算法。为了较好地分析它,在此对它作一简述。该算法是针对Dijkstra算法中的步骤3做的优化。按照Dijkstra算法来计算,从未标记为红点的顶点中选择一个D(vi)最小
储问题放在了一个重要的位置,以牺牲适当的时间效率来换取空间节省,排序优化算法将时间放在了第一位,在提高时间效率方面有较好的应用性。
本文提出的快速Dijkstra最短路径优化算法是将提高时间效率放在第一位,以十字链表结构记录
收稿日期:2004-09-09作者简介:司连法(1973-),男,河南商丘人,工程师,现从事电子地图、GIS程序开发以及地理学的研究。
( 2005) 0820015204 关键词 :Dijkstra 算法 ; GIS ; 最短路径 ; 优化 中图分类号 : P208 文献标识码 :B 快速 Dijkstra 最短路径优化算法的实现司连法1 ,...
Dijkstra最短路径算法的实现及优化_IT/计算机_专业资料。基于Dijkstra的算法分析Dijkstra 最短路径算法的实现及优化 施培港 厦门信息港建设发展股份有限公司 厦门市...
您的论文得到两院院士关注 文章编号 :1008-0570(2007)11-3-0275-03 软件时空 Dijkstra 最短路径算法的优化及其实现TheoptimizationandImplementationoftheShortestPath...
Dijkstra最短路径算法的... 4页 免费 快速Dijkstra最短路径优... 4页 1...在实际的算法实现过程中 , 权值排序可以在数据准备 阶段实现 , 而无须在运算...
Dijkstra最短路径算法的优化及其实现_王志和_工学_高等教育_教育专区。您的...下面将就如何用一个简洁高效的结构表示网的拓 扑关系以及快速搜索技术的实现进行...
Dijkstra最短路径算法优化_天文/地理_自然科学_专业资料。Dijkstra最短路径算法...j 由以上算法步骤可知, 用标记法实现 D ijk stra算法的主要步骤是从未标记的...
用标 记法 实现 Djsa算法的 主要 步 骤是 从未标记的节点 中选 择一个...G 施行优化 Djt 算法 , ,对,isakr则 可得从 到其余各节点的最短路径 , ...
举例说明了该算法的实现方法以及该算法的缺点: 即需要 网络结点 数平方级的 内存; 同时详细说明了一种基于 Dijkstra 算法的优化算法 邻接 结点算 法, 该 算法充...
高速公路网中的Dijkstra... 7人阅读 4页 2.00基于最短...(0).N20 1 基 于最短路径优化 问题 Djsritk a算法程序的设计 和实现 岳秋...
Dijkstra最短路径算法的优化和改进_天文/地理_自然科学_专业资料。随着计算机和...为了科学有效 的实现这些目的,就需要引入新的技术来解决问题.计算机技术的发展为...
热门文档