文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 理学 > 快速Dijkstra最短路径优化算法的实现
侵权投诉

快速Dijkstra最短路径优化算法的实现

运筹学资料

快速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程序开发以及地理学的研究。

第1页

你可能喜欢

  • 最短路径算法
  • Dijkstra算法代码
  • Dijkstra算法应用
  • 迪杰斯特拉算法
  • 运筹学熊伟课后习题答案
  • 蚁群算法 matlab
  • 车辆路径优化问题

热门文档

相关文档

  • 快速Dijkstra最短路径优化算法的实现

    ( 2005) 0820015204 关键词 :Dijkstra 算法 ; GIS ; 最短路径 ; 优化 中图分类号 : P208 文献标识码 :B 快速 Dijkstra 最短路径优化算法的实现司连法1 ,...

  • Dijkstra最短路径算法的实现及优化

    Dijkstra最短路径算法的实现及优化_IT/计算机_专业资料。基于Dijkstra的算法分析Dijkstra 最短路径算法的实现及优化 施培港 厦门信息港建设发展股份有限公司 厦门市...

  • Dijkstra最短路径算法的优化及其实现

    您的论文得到两院院士关注 文章编号 :1008-0570(2007)11-3-0275-03 软件时空 Dijkstra 最短路径算法的优化及其实现TheoptimizationandImplementationoftheShortestPath...

  • Dijkstra最短路径算法优化策略

    Dijkstra最短路径算法的... 4页 免费 快速Dijkstra最短路径优... 4页 1...在实际的算法实现过程中 , 权值排序可以在数据准备 阶段实现 , 而无须在运算...

  • Dijkstra最短路径算法的优化及其实现_王志和

    Dijkstra最短路径算法的优化及其实现_王志和_工学_高等教育_教育专区。您的...下面将就如何用一个简洁高效的结构表示网的拓 扑关系以及快速搜索技术的实现进行...

  • Dijkstra最短路径算法优化

    Dijkstra最短路径算法优化_天文/地理_自然科学_专业资料。Dijkstra最短路径算法...j 由以上算法步骤可知, 用标记法实现 D ijk stra算法的主要步骤是从未标记的...

  • Dijkstra最短路径算法优化

    用标 记法 实现 Djsa算法的 主要 步 骤是 从未标记的节点 中选 择一个...G 施行优化 Djt 算法 , ,对,isakr则 可得从 到其余各节点的最短路径 , ...

  • 基于Dijkstra算法的一种最短路径优化算法

    举例说明了该算法的实现方法以及该算法的缺点: 即需要 网络结点 数平方级的 内存; 同时详细说明了一种基于 Dijkstra 算法的优化算法 邻接 结点算 法, 该 算法充...

  • 【论文】基于最短路径优化问题Dijkstra算法程序的设计...

    高速公路网中的Dijkstra... 7人阅读 4页 2.00基于最短...(0).N20 1 基 于最短路径优化 问题 Djsritk a算法程序的设计 和实现 岳秋...

  • Dijkstra最短路径算法的优化和改进

    Dijkstra最短路径算法的优化和改进_天文/地理_自然科学_专业资料。随着计算机和...为了科学有效 的实现这些目的,就需要引入新的技术来解决问题.计算机技术的发展为...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email