毕业设计-基于DIJKSTRA的最短路径搜索算法的优化及应用论文.doc

毕业设计（论文）题 目 基于dijkstra的最短路径搜索算法的优化及应用 姓 名 学 号 专业班级 指导教师 分 院 完成日期 摘 要最短路径分析是gis地理网络分析功能中的一个关键问题。dijkstra算法是计算最短路径的经典算法，是许多工程解决最短路径问题的理论基础。传统dijkstra算法在求解节点间最短路径时，对已标识节点以外的大量节点进行了计算，从而影响了算法的速度。本文在对传统dijkstra算法分析的基础上，对其进行了优化，优化算法只对最短路径上节点的邻居做了处理，而不涉及到其他节点。因此，在优化算法中计算的节点数大幅减少，提高了算法的速度。本文通过实验和实际应用对改进后的算法进行了验证。关键词：最短路径；dijkstra算法；优化abstractshortest path analysis is the key problem of network analyses， dijkstra algorithm is a classic arithmetic for the shortest path. it is the academic foundation that many engineerings were solved in the shortest path issue. when a shortest path between nodes is searched with dijkstra algorithm，a lot of nodes away from lagged nodes are involved，so that the efficiency of dijkstra algorithm is lowan optimization algorithm is presented in this paper based on analysis of dijkstra algorithmonly these nodes that the neighbor of nodes in the shortest path are processed，and other nodes are not processed. therefore，the number of processed nodes is largely reduced in the optimization algorithm，and efficiency of the optimization algorithm is improvedthe improved algorithm is proved to be correct and efficient by experiments and practical application.keywords: the shortest path；dijkstra algorithm；optimizationii目 录摘 要iabstractii第1章概述11.1国内外最短路径算法概况11.1.1国内外最短路径研究的主流与方向11.1.2国内外主流算法及其简要展开a*算法3遗传算法4dijkstra算法31.1.3经典dijkstra算法存在的问题41.2研究的意义41.3本文研究目标和内容4第2章dijkstra经典算法研究62.1dijkstra算法的原理及应用62.1.1dijkstra算法原理62.1.2dijkstra算法应用72.1.3dijkstra算法的优缺点102.2以dijkstra算法为基础算法进行优化的原因122.2.1dijkstra算法与其他主流算法的比较5搜索速度比较搜索成功率比较13第3章dijkstra优化算法研究143.1多种dijkstra优化算法的研究6143.1.1第一类优化算法减小算法中成功搜索的搜索范围143.1.2第二类优化算法改进算法的存储结构143.2本文对dijkstra优化算法的研究153.2.1优化算法的目标153.2.2优化算法思路153.2.3优化算法描述163.2.4优化算法的特点203.3优化dijkstra算法与原dijkstra经典算法比较20第4章优化dijkstra算法的应用214.1优化算法在上海市物流中的实现214.1.1地图说明214.1.2属性数据库设计224.1.3算法实现234.1.4算法优化前后对比25第5章总结与展望265.1全文总结265.2展望26参考文献27附 录29致 谢35iii第1章 概述1.1 国内外最短路径算法概况1.1.1 国内外最短路径研究的主流与方向最短路径这一重要问题早在20世纪初就已经得到人们的高度重视，当时也有许多科学家研究这一重要问题的求解方法。但直到1959年荷兰计算机科学家edsger wybe dijkstra (迪杰斯特拉)才给出这一问题求解的基本思想，并给出了算法。当时的dijkstra提出的这一算法主要解决的问题是从固定的一个点到其他各点的最短路径问题。后来这个算法就成了众所周知的dijkstra算法，也成为了一代经典。1 现今比较流行的最短路径规划算法主要有以下三类：第一类是基于图论理论的算法；如dijkstra及其改进算法，floyd算法等；第二类则是基于传统人工智能理论的算法，如a*机器改进算法，深度有限、宽度有限算法等；第三类则是基于智能控制技术的算法，如人工神经网络算法、遗传算法等。特别是近10年来，智能控制技术在路径规划问题中得到广泛的应用，人们的研究兴趣也逐渐从对前两类算法的改进转到了对第三类算法的进一步研究中。当前对于最短路径的相关研究主要包含两方面。第一方面为最短路径问题（完全信息情况下）。在这种确定情况下最短路径问题的研究中，bellman（1958）、dijkstra（1959）和dreyfus（1969）已发展出许多高效算法。这些算法已成为确定情况下的经典算法。在不确定的情况下最短路径问题的研究包含以下几个方面：frank（1969）和mirchandani（1976）研究了路段长度随机变化的且非时间独立的情况下的最短路径问题；loui（1983）、muethy和sarkar（1996）考虑不同的费用函数研究最短路径问题，他们的结论是当目标是期望最短路径时问题转化为将边的权重用期望值表示的最短路径问题；hall（1986）、liping fu和l.r.rilett（1998）、elise和hani（2000）研究了路段长度随机变化且时间独立情况下的最短路径问题；tomas和rajeev研究了路段长度为区间范围的最短路径问题。21.1.2 国内外主流算法及其简要展开 a*算法3a*（a-star)算法是一种静态路网中求解最短路最有效的方法。公式表示为：f(n)=g(n)+h(n)其中f(n) 是节点n从初始点到目标点的估价函数，g(n) 是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：估价值h(n)实际值, 搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。估价值与实际值越接近，估价函数取得就越好。a*算法是人工智能中一种典型的启发式搜索算法，算法的创新之处在于选择了下一个被探索的结点时引入了已知的路网信息和目标点信息，对当前点与终点的距离进行评估，作为选择下一路径结点的依据。通用的a*算法可采用四方向，八方向，对于矢量路网则可采用遍历相连路径法进行路径探索。在城镇地价定级估价中，不考虑路网，可采用栅格八方向法。通过a*算法可以寻找任何一个因素因子与其它各点之间的最短路径。它不用遍历整个搜索空间，而是根据所选择的启发式函数朝着最有希望的方向前进。它的搜索速度虽然较快，理论上也能找到最优解，但在实际应用过程中往往由于启发式函数选取不当而经常找不到最短路径，搜索的成功率并不是很高。 遗传算法4遗传算法（genetic algorithms，简称ga）是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。它的思想源于生物遗传学和适者生存的自然规律，是具有“生存+检测”的迭代过程的搜索算法。ga把每一个可能的解编码为一个向量，称为一个染色体，向量的每一个元素称为基因。所有染色体组成群体。并按预定的目标函数对每个染色体进行评价，根据其结果给出一个适应度的值。算法开始时先随机地产生一些染色体，计算其适应度，根据适应度对诸染色体进行选择、交换、变异等遗传操作，剔除适应度低的染色体，留下适应度高的染色体。由于新群体的成员是上一代群体的优秀者，因而在总体上优于上一代。ga就这样反复迭代，直至满足某种预定的优化指标。上述ga的工作过程可用图1.1简要描述。y问题的初始（侯选）解种群满足预定指标编码为染色体（向量）种群p（t）计算各染色体适应度通过遗传运算存优去劣种群p（t+1）复制交换变异种群p（t）种群p（t+1）解码染色体问题解答空间n图 1.1 遗传算法工作原理示意图 dijkstra算法dijkstra算法的基本思想是，设置一个顶点的集合s，从源点s到集合中的各顶点的最终最短路径的权值均已经确定。算法反复选择具有最短路径估计的顶点 ivs，并将i加入s中，对i的所有出边进行松弛（本文第2章节将对经典dijkstra算法做详细研究）。1.1.3 经典dijkstra算法存在的问题（1）原始dijkstra算法在存储图形数据和运算时，基于网络的权矩阵，需要根据其节点与距离之间的关系，形成关联矩阵、邻接矩阵与距离矩阵，需要定义nn的数组来存储数据，其中n为网络的节点数，当网络的节点数较大时，将占用大量的计算机内存。（2）原始dijkstra算法在运行时一般将网络节点分为未标记节点、临时标记节点和永久标记节点3种类型。网络中所有节点首先初始化为未标记节点，在搜索过程中和最短路径节点相连通的节点为临时标记节点，每一次循环都是从临时标记节点中搜索距离原点路径长度最短的节点作为永久标记节点，直至找到目标节点或者所有节点都成为永久标记节点才结束算法。根据算法的描述可知对临时标记节点的遍历成为dijkstra算法的瓶颈，影响了算法的执行效率。1.2 研究的意义随着社会的不断进步，最短路径算法在人们的日常生活显得越来越重要。每天开车去上班，应该选择哪条公路才能使自己到公司的费用最低、时间最少，这是最短路径的问题；在网络路由中，怎样选择最优的路由路径，这也是最短路径问题；在交通旅游、城市规划以及电网架设中怎样使其耗费的资金最少，这还是最短路径问题。由此可见对最短路径问题的研究是非常有意义的。最短路径算法是计算机科学与地理信息科学等领域研究的热点，其算法有很多种，其中传统的dijkstra 算法一般用于计算一个源节点到所有其他节点的最小代价路径，并且能够适应网络拓扑的变化，性能稳定，因而可以在运输路线规划等领域都应用广泛。1.3 本文研究目标和内容dijkstra算法的空间复杂度o(n2)，采用邻接矩阵存储网络拓扑结构，需要（nn）的存储空间，查询速率较快，在数秒内即可完成查询，所用时间在用户的容忍范围内。但dijkstra算法随着节点数n的增大，其计算效率和存储效率越低。所以针对地理信息中的海量信息需要寻求算法优化，对dijkstra算法优化的思路主要有：缩小节点的搜索范围，只对最短路径上节点的邻居作处理，而不涉及相离节点的其他节点。算法优化思想：首先从与起点s直接相连的相邻节点几个nbk中选择距离最小的节点k作为转接点，同时将k划归为表示集合s（初始时，s为s）。然后对k另据集合与表示集合的差集，（nbk - s）中节点j的wj值进行更新，从标识集合s中所有节点的邻居集合的并集与标识集合s的差集（nbi - s,is）中选择一个wk值最小的节点作为下一个转接点，并划归为到标识集合s中。重复上述过程，直到所有的节点都被标识过，即s=n，算法结束。由于现实中只需要查询起点和终点间的最短路径，而不需要求出起点到多有节点的最短路径，所以根据需要只要找到起点到终点的最短距离即可退出循环处理过程，缩短查询时间。dijkstra算法的核心步骤，即从具有临时标号的节点中搜索与起点距离最小的节点，如果具有临时标号的节点无序地存放在数组中，则每次迭代都要把所有未获得永久标号的都扫描一遍，所以将具有临时标号的节点按与起点距离大小进行排序则可以节省每次扫描的时间，提高查询速率。改进数据的组织结构，用类或结构体来组织节点、线路并建立拓扑关系可以提高数据搜索效率。第2章 dijkstra经典算法研究2.1 dijkstra算法的原理及应用2.1.1 dijkstra算法原理dijkstra算法是1959年由ewdijkstra提出的图论中求最短路径的一个著名的算法，使用其可以求得图中一点到其他各顶点的最短路径。原始的dijkstra算法将网络结点分成3部分：未标记结点、临时标记结点和永久标记结点。网络中所有结点首先初始化为未标记结点，在搜索过程中和最短路径中的结点相连通的结点为临时标记结点，每次循环都是从临时标记结点中搜索距源点路径长度最短的结点作为永久标记结点，直至找到目标结点或者所有的结点都成为永久标记结点来结束算法。假设每个点都有一对标号 (wj, pj)，其中wj 是从起源点s到点j的最短路径的长度 (从顶点到其本身的最短路径是零路(没有弧的路)，其长度等于零)；pj 则是从s到j的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法的基本过程如下：1)初始化。起源点设置为： ws=0, ps为空； 所有其他点: wi=, pi=?；标记起源点s，记k=s,其他所有点设为未标记的。2)检验从所有已标记的点k 到其直接连接的未标记的点j的距离，并设置：wj=min wj, wk+dkj 式中，dkj 是从点k到j的直接连接距离。3)选取下一个点。从所有未标记的结点中，选取wj中最小的一个i：wi=min wj，（所有未标记的点j），点i就被选为最短路径中的一点，并设为已标记的。4)找到点i的前一点。从已标记的点中找到直接连接到点i的点j*，作为前一点，设置：i=j*。5)标记点i。如果所有点已标记，则算法完全推出，否则，记k=i，转到2)再继续。dijkstra算法最短路径应用演示图 2.1 dijkstra算法最短路径应用演示图 表 2.1 从0节点到4节点的最短路径循环红点集skd0d1d2d3d4p0p1p2p3p4初始化0-01030100-10-10010,110106030100-1010020,1,33010503090-1030330,1,3,22010503060-1030240,1,3,2,44010503060-103022.1.2 dijkstra算法应用给定简单无向图g,指定一顶点vi为起点,对于任意 vjg 且ij,求vi到vj 的最短路径的长度。例:北京的小汤山医院已经投入使用了,在抗击非典的战役中发挥了重要的作用。现在,在北京市内有若干家收治非典病人的医院。各个医院之间的路程和各医院到小汤山之间的路程已知(有可能没有直通道路),由于非典病人的特殊性,在往小汤山转运的过程中只能在收治病人的医院中转。现在,党和政府交给了你一个光荣而艰巨的任务,计算出小汤山到市内各收治医院的最短路径,为抗非事业做出你应有的贡献。给定问题的算法分析:1)初始化：起点的最短路径为0，其他顶点的最短路径为，所有顶点未标号。2)在所有未标号的顶点中找出最短路径最短的顶点i。若无法找到，则说明所有顶点已标号，或者所有的未标号顶点都是无法到达的，转5)。3)更改所有与i直接相邻的未标号顶点的最短路径。更新方法如下：如果i的最短路径边ij 的长度距离2,所以不更新)医院1已标号距离0医院2未标号距离12医院3已标号距离4医院4以标号距离912456找所有未标号中距离最短的顶点为医院2,将2做标号,已没有与2相邻的未标号顶点需要更新了医院1已标号距离0医院2已标号距离医院3已标号距离4医院4已标号距离912456再次找所有未标号中距离最短的顶点已找不到,得结果d(2)=12,d(3)=4,d(4)= dijkstra算法的优缺点dijkstra算法能够保证100%找到最优解，但其搜索速度较慢，搜索效率非常低，时间花费较多，一般只能用于离线的路径规划问题。如节点数为n的图，用dijkstra算法计算最短路径总共需要迭代n一1次，每次迭代都新加一个节点到临时节点集合中，由于第i次迭代时不在临时节点集合中的节点数为n-i即第i次迭代需对n-i个节点进行处理，因此其所需的处理数为，对n个节点网络的时间复杂度是o(n2)。在实际应用当中，使用dijkstra算法查找最短路径时耗费大量的时间进行数据的比较，本文对dijkstra算法进行分析，通过改变算法实现减少不必要节点计算的时间，提高算法的效率达到对其进行优化。下一个例子说明dijkstra算法存在的缺陷：例：图2.2所示为一带权图g(v，e，w)，求从v1出发到其它各个顶点的最短路径长度。图 2.2 权图g解：wi表示由源v1到点vi的最短距离；s表示已求出最短路径的顶点集合，其初始值为sv1；k表示刚选出的顶点的编号；选出vk后修改u中各顶点的距离的方法为：wi=minwi，dki；下表通过dijkstra算法来求解图2.2的最短路径长度：v1初始第一步第二步第三步v2159v3v44v5v610v7s=v1v4v2kwsv1,v4v1,v2,v4在上表中选出顶点v4加入到s时一共进行了6次比较，其中四次是与作比较，也就是说这四次完全没有必要进行比较。当选出v4后，需要对u中的各个顶点的距离进行调整，在调整过程中利用到wi =minwi，w4+d4i其中i1，4(1，4已经在s中)即需要对wi和w4+d4i进行比较，但我们在对w3,w5,w7进行调整时可以发现由于d43，d45，d47 e(g)即它们的权值为，所以调整时是没有必要进行比较的，在这里多进行了3次比较。后面的各步也都出现类似的情况(后略)，尤其是当图的边数相对较少时更为明显。2.2 以dijkstra算法为基础算法进行优化的原因2.2.1 dijkstra算法与其他主流算法的比较 搜索速度比较对5张图分别采用dijkstra算法、a*算法、遗传算法进行路径规划，他们各自花费的时间如表2.2所示。表 2.2 三种算法在搜索速度上的对比节点数搜索速度dijkstra算法a*算法遗传算法1611232424437366215597825712由表2.2可以看出：当地图节点个数和弧的条数比较少时，三种算法所花费的时间差不多，当节点个数和弧的条数比较多时，a*算法最快，遗传算法其次，dijkstra算法最慢，而且这种差距将随节点和弧数量的增加而变得更加明显。对于实际地图而言，由于节点与道路的数量一般都很的大，dijkstra算法在搜索速度方面弱势明显。 搜索成功率比较对于具有n个节点的地图，其待规划节点的个数为n-1（除起点节点外，其他均可作为待规划节点），由于每个待规划节点对应于一条最短路径，所以对每张具有n个节点的地图而言，应该规划出n-1条最短路径。对5张地图分别采用三种算法进行路径规划，三者各自搜索到最短路径的情况如表2.3所示。表中括号外数据为各算法实际得到最短路径数，括号内数据则为各算法实际得到路径数和应该规划出的最短路径数n-1之比。表 2.3 三种算法在搜索质量方面的对比节点数dijkstra算法a*算法遗传算法1615(100%)12(80%)15(100%)3231(100%)25(81%)29(94%)4342(100%)32(76%)38(90%)6261(100%)40(66%)56(92%)7877(100%)45(58%)71(92%)由表2.3可以看出：当地图节点个数和弧数量比较多时，dijkstra算法是一种遍历算法，每次能保证100%搜索到最短路径，遗传算法搜索到最短路径的成功率比dijkstra算法低一些，a*算法最低，且这种差距在节点数和弧数量越大时更加明显。第3章 dijkstra优化算法研究3.1 多种dijkstra优化算法的研究63.1.1 第一类优化算法减小算法中成功搜索的搜索范围减小算法中成功搜索的搜索范围以尽快到达目标节点。在对现实问题中的交通图初始化为网络拓扑图时，虽然终点已知，而源点尚未确定，但依据常识离案发地段最近的派出所应为案发地段所在辖区派出所，或其周边派出所，也就是源点的选取范围可以确定。利用mapobjects2组件提供的maplayer.searchexpression (expression)记录集筛选方法，根据案发地段(终点)的不同，动态选取案发地段所在辖区及相邻辖区的道路图层及派出所图层数据进行最短路径查询，从而有效地减少了拓扑图中节点总数n的值。3.1.2 第二类优化算法改进算法的存储结构在实际工作中，还要建立起空间数据结构。网络数据结构使用的是“边和节点”的数据结构，该数据结构是建立在图论的基础上，节点可用来定义边的连接关系。对于网络数据的存储，传统的是采用图论中的邻接矩阵方法，其存储量为n n(n为网络中节点数)。通常的地理网络，尽管节点很多，但与节点相关联的节点数目并不多，一般都为稀疏图，将会浪费大量的空间。若采用邻接表的链式存储结构，其存储量为e(e为节点列表中，同节点关联的所有边的数目)，可节省大量的存储空间，尤其是在表示与节点和边相关信息较多的地理网络时，更为有效。但邻接表却难以判断两节点之间的关系，因此本文提出利用。net框架提供的特殊类hashtable。.net框架包含特殊类，比如通常所说的集合类用于存储对象。与数组类似，集合类可以把对象放入容器中，然后再取出但集合的使用方法与数组不同，拥有用于插入和删除项的专用方法。使用hashtable最大的优点就是大大降低数据存储和查找的时间花费，几乎可看成是常数时间。3.2 本文对dijkstra优化算法的研究本文采用第一类优化算法减小搜索范围的思路对dijkstra算法进行优化。3.2.1 优化算法的目标dijkstra算法用来求解图上从任一节点(源点)到其余各节点的最短路径。其时间复杂度为o(n2)；采用邻接矩阵存储网络拓扑结构，需要(nn)的存储空间，随着节点数n的增大，其计算效率和存储效率越低。针对此问题，提出了dijkstra算法的改进，本文在对传统dijkstra算法分析的基础上，对其进行了优化，优化算法只对最短路径上节点的邻居做处理，而不涉及到其他节点。3.2.2 优化算法思路dijkstra算法基本方法：设wj是从源点s到节点j的最短路径长度；pj是从s到j的最短路径中j点的前一节点。s是标识集合；t是未标识集合；m是节点集合dij提节点i到节点j的距离(i与j直接相连，否则dij = )算法步骤如下：step0：s = s；t = m-s；wj = dij(jt，s与j直接相连)或 wj = (j t，s与j不直接相连)。step1：在t中找到节点i，使s到i的距离最小，并将i划归到s。(可从与s直接相连的j中考虑)若dsi = min dsj j与s直接相连，则将i划归到s中，即s =s，i，t = t-i；jtpi =s。step2：修改t中j节点的wj值：wj = min(wj,wi + dij)；若wj值改变，则pj = i jtisstep3：选定所有的wj最小值，并将其划归到s中：wi = min wj； s=si；t=t-i；若s= n, 所有节点已标识，则算法终jt止，否则，转人step2。通过分析传统dijkstra算法的基本思路，传统dijkstra算法存在如下两点不足：(1)当从未标记节点集合t中选定一个节点k作为转接点后时，需扫描未标记节点集合t中的节点j并更新其wj值，而未标记节点集合t中往往包含大量与转接节点k 不直接相连的节点i(即dki = )；(2)在未标记节点集合t中选择一个w值最小的节点作为下一个转接节点，然而下一个转接节点往往是与标记节点集合s中的节点直接相连的。3.2.3 优化算法描述基于上述两点不足，对传统dijkstra算法进行优化，算法优化思路为：首先从源点s的邻居集合nbs(与s直接相连的节点集合)中选择距离最小的邻居节点k作为转接点，同时将划归到标识集合s(初始时，s为s)。然后对k邻居集合与标识集合的差集(nbk - s)中节点的值进行更新，从标识集合s中所有节点的邻居集合的并集与标识集合的差集(nbs - s，is)中选择一个wk值最小的节点作为下一个转接点，并划归到标识集合s中。重复上述过程，直到所有的节点都被标识过，即s=n，算法结束。设nbi为节点i的邻居集合；s为标识集合； wj是从源点s到节点j的最短路径长度；pj是从s到j的最短路径中j点的前一节点；dij是节点i到节点j的距离。算法步骤如下：step0：初始化s = s；wi = dsi(inbs)；否则 = (i nbs)；pi=s。step1：若dsk = min dsj ，则s = s k。 jnbsstep2：修改nbk - s中的wj值：wj = min wj,wk +dkj ；若wj值改变，则 pj = k。jnbs -sstep3：选定nbi - s(is)中的wj最小值，并将其划归到s中： wk = min wj；s = s k；若s= n；所有节点已标识，则算法终止， jnbssis否则，转到step2图3.1为带权值的无向图g7，对g7分别用dijkstra算法和优化了的dijkstra算法进行求解，则可得从v1到其余各节点的最短路径。图 3.1 非负权值图经典dijkstra算法求解过程：step0：初始化s = (v1)，w1 = 0，t = (v2,v4, v3,v5, v6,v7)；step1：w4 = d14 = mind1j = 2（d12 = d14，任选其一，本文选v4），s = (v1,v4)，t = jt(v2,v3,v5,v6,v7)；step2：t = (v2,v3,v5,v6,v7)w2 = minw2，w4 + d42= min2，4= 2，w3 = minw3，w4 + d43= min5,5 = 5 2 = w2，w5 = minw5，w4 + d45 = ，3 = 3 2 = w2，w6 = minw6，w4 + d46 = ， (3.1)w7 = minw7，w4 + d47 = ， (3.2)minwj =w2 = 2，s = (v1,v2,v4)，t = (v3,v5,v6,v7)；step3：t = (v3,v5,v6,v7)w3 = minw3，w2 + d23 = min5,5 = 5，w5 = minw5，w2 + d25 = min3, = 3 5 = w3，w6 = minw6，w4 + d46 = ， (3.3)w7 = minw7，w4 + d47 = ， (3.4)minwj = w5 = 3，s = (v1,v2,v4,v5)，t = (v3,v6,v7)；step4：t = (v3,v6,v7)w3 = minw3，w5 + d53 = min5,4 = 4，w6 = minw6，w5 + d56 = ，4 = 4 = w3，w7 = minw7，w5 + d57 = ，5 = 5 4 = w3 = w6，minwj = w3 = w6 = 4，任选其一，若为w3，s = (v1,v2,v3,v4,v5)，t = (v6,v7)；step5：t = (v6,v7)w6 = minw6，w3+d36= min4， = 4，w7 = minw7，w3 + d37 = 5， = 5 4 = w3 = w6，minwj = w6 = 4，s = (v1,v2,v3,v4,v5,v6)，t = (v7)；step6：t = (v7)w7 = minw7，w6 + d67 = 5，6 = 5。至此，所有节点已标识，则算法终止。最终结果为w2 = 2，w3=4，w4=2，w5=3，w6=4，w7=5，w6=4，w7=5。优化dijkstra算法求解过程：表 3.1 优化的dijkstra算法求解v1 到其他各节点最短路径的过程迭代次数v1v2v3v4v5v6v7选定点winbisnbi-snbi-s01252v1w1=0(v2,v3,v4)(v1)125v4w4=2(v1,v2,v3,v5)(v1,v4)(v2,v3,v5)(v2,v3,v5)243v2w2=2(v1,v3,v4)(v1,v2,v4)(v3)(v3,v5)34v5w5=3(v3,v4,v6,v7)(v1,v2,v4,v5)(v3,v6,v7)(v3,v6,v7)445v3w3=4(v1,v2,v4,v5,v6)(v1,v2,v3,v4,v5)(v6)(v6,v7)55v6w6=4(v3,v5,v7)(v1,v2,v3,v4,v5,v6)(v7)(v7)6v7w7=5(v5,v6)(v1,v2,v3,v4,v5,v6,v7)step0：初始化s = (v1)，与v1直接相连的点有v2v3v4，nb1 = (v2,v3,v4)，w1 = 0；step1：w4 = d14 = mind1j = 2（d12 = d14，任选其一，本文选v4），s = (v1,v4)，nb4 = jnb1(v1,v2,v3,v5)，nb4 s = (v2,v3,v5)，nb4-s = (v2,v3,v5)； step2：jnb4 s = (v2,v3,v5)w2 = minw2，w4 + d42= min2，4= 2，w3 = minw3，w4 + d43= min5,5 = 5 2 = w2，w5 = minw5，w4 + d45 = ，3 = 3 2 = w2minwj =w2 = 2，s = (v1,v2,v4)，nb2 = (v1,v3,v4)，nb2-s = (v3)，nb2-s = (v3,v5)；step3：jnb2-s = (v3,v5)w3 = minw3，w2 + d23 = min5,5 = 5，w5 = 3 5 = w3，minwj = w5 = 3，s = (v1,v2,v4,v5)，nb5 = (v3,v4,v6,v7)，nb5-s = (v3,v6,v7)，nb5-s = (v3,v6,v7)；step4：jnb4 s = (v3,v6,v7)w3 = minw3，w5 + d53 = min5,4 = 4，w6 = minw6，w5 + d56 = ，4 = 4 = w3，w7 = minw7，w5 + d57 = ，5 = 5 4 = w3 = w6，minwj = w3 = w6 = 4，任选其一，若为w3，s = (v1,v2,v3,v4,v5)，nb3 = (v1,v2,v4,v5,v6)，nb3-s = (v6)，nb3-s = (v6,v7)；step5：jnb3-s = (v6,v7)w6 = 4w7 = 5 4 = w6，minwj = w6 = 4，s = (v1,v2,v3,v4,v5,v6)，nb6 = (v3,v5,v7)，nb6-s = (v7)，nb6-s = (v7)；step6：jnb6 s = (v7)w7 = minw7，w6 + d67 = 5，6 = 5。至此，所有节点已标识，则算法终止。最终结果为w2 = 2，w3=4，w4=2，w5=3，w6=4，w7=5，w6=4，w7=5。3.2.4 优化算法的特点传统dijkstra算法基于广度优先的搜索策略，从指定节点出发，通过权值迭代遍历所有其他节点后，最后得到从指定节点到其他各节点的最短路径树。它采用线性数组结构存储其关联矩阵，在提取最短路径节点时需要访问所有的未标记节点，算法的运行时间为o(n2)。本文提出的优化算法在更新最短路径值与选择最短路径值最小的节点时，仅仅涉及到节点的邻居集合及已标识集合中所有节点的邻居集合与已标识集合的差集，其运行时间取决于转接点的邻居集合的元素数量多少(而该数量值往往小于未标识集合中的元素个数)。优化算法空间复杂度为o(np)，其中p是常量，为结点对象所占用的空间。另外，根据图中顶点和边的个数，可以求出顶点的平均出度e=mn(m为边数，n为顶点数)，一般在gis的网络图中，e2，5，由于step2、step3都是搜索与vi(i=l，2，3,，n)相邻的结点操作，时间复杂度均为o(ne)；step3的时间复杂度为o(m)，即o(ne)；步骤(5)的时间复杂度为o(ne)。因此，算法的时间复杂度为o(ne)。3.3 优化dijkstra算法与原dijkstra经典算法比较由3.2.3章节对带权值的无向图g7的求解可以看出，优化了的dijkstra算法在step2和step3中较经典的dijkstra算法减少了步骤(3.1)(3.2)(3.3)(3.4)，减少了计算次数，提高了搜索速度。当网络拓扑结构图具有的节点数，v较大且其关联矩阵为一个稀疏矩阵时，相对传统dijkstra算法，优化算法大大减少了计算次数与比较次数，在一定程度上提高了运算速度。在分析传统dijkstra算法的基础上，针对传统dijkstra算法存在的两点不足之处，对其进行了优化处理。当网络的规模较大及其关联矩阵为一个稀疏矩阵时，本文提出的优化算法，与传统dijkstra算法相比，能大大减少了计算次数及比较次数，提高了运算效率。45第4章 优化dijkstra算法的应用4.1 优化算法在上海市物流中的实现4.1.1 地图说明上海，中国最繁华的城市之一，是我国的优秀旅游城市。鉴于其节点多路段复杂的特性，我们以上海市地图为例。本文采用c#语言实现了改进算法，并在intel p4-m、512ram运行环境下，对总共有81339条弧、60828个节点的上海市地图进行实际测试，上海市交通道路组成如图4.1所示。图 4.1 上海市地图4.1.2 属性数据库设计本系统属性数据用关系数据库sqlserver2000 统一管理，我们将81339条弧、60828个节点按上海市实际情况划分92个区域。系统属性数据主要包括两类：节点表数据，边表数据。节点表（nshanghai）包含了上海市各节点信息，主要包括节点编号、所在区域、与其相邻的路段等其他相关信息，结构设计如表4.1：表 4.1 节点表（nshanghai）字段名称字段类型字段解释mapidchar区域编号idchar节点编号node_lidchar相邻路段编号边表（rshanghai）包含了上海市各路段信息，只要包括路段编号、所在区域、路段起点、路段终点等其他相关信息，结构设计如表4.2：表 4.2 边表（rshanghai）字段名称字段类型字段解释mapidchar区域编号idchar路段编号snodeidchar起点编号enodeidchar终点编号本实验采用节点命名规则：节点id前6位表示区域mapid，如：46616300077节点的前6位466163表示节点所在区域mapid为466163，后5位根据节点个性命名。4.1.3 算法实现为方便起见我们将任意相邻两点间是距离预设为1，即dij = 1。这样，设结果显示最短路径为10，可知起点终点之间经过10个路段长度，经过9个中间转折点。程序设置地图拖动、放大、缩小、载入空间拓扑、计算最短路径等功能，如图4.2。图 4.2 地图功能展示程序运行后，首先载入网络拓扑，读取数据库信息：载入网络拓扑载入网络拓扑载入原始节点载入原始边完成（空间拓扑共有60828个节点）图 4.3 网络拓扑载入过程例：我们选取同区域不相邻两节点进行算法实现，设置起点46616300077，终点46616300087，实验结果如图4.4、4.5：图 4.4 经典dijkstra算法实现图 4.5 dijkstra优化算法实现如图4.4、4.5，相同的起点终点，所得最短路径长度均为30，经典dijkstra算法经过对区域编号为466163、含有5563个节点的区域进行节点遍历后共用时12秒，而dijkstra优化算法对s内节点的邻居节点进行遍历后只用时8秒，提高了搜索效率。4.1.4