Dijkstra算法的优化研究

科技研究Dijkstra算法的优化研究马翠杰孙晓琳烟台南山学院物流学院山东烟台265713[摘要]D1jkstra算法是典型最短路算法，用于计算网络图中一个节点到其他所有节点的最短路径。但由于它计算所经过的的节点很多，并且会有很多重复计算的步骤,所以效率低。本文主要从算法所需要计算的主要步骤来考虑，提出可能节省时间的一些有效措施。!关键词]Dijkstra算法最短路径[ Abstract I Dijkstra algorithm is a typical Algorithm used to calculate the shortest path.It Calculstes from one node to the other nodes to resut to theshortest path.But because it traveis among too much nodes,that it is low fficiency.This article Consider the main steps calculated to make it much easy切0 save time and become much effective.[Key Words ] agritm of Dinksra;The shoret Dath中圈分类号: TP39文献标识码: B文章编号: 1009 4672011)03-94-010Dijkstra算法用于求解- -个有 向图(也可以是无向图.无向園是有向圈d+w.d,的一种特例)的一个点(称之为原点)到其余各点(称之为周边点)的最短如果满足条件再记下有向边(v,"),依次继续,直到得到有向边(v,路径问题。算法主要特点是以起始点为中心向外层层扩展,直到寻找到到目v、)为止。如果不满足.则返问到终点Vt的其它先行节点循环进行反向追踪。的节点为止。Dijkstra算法能得出最短路径的最优解，Dijikstra算法可以直到得到从v。到v,的最短路径:看做是广度优先搜索的变种"也可以被认为是启发性搜索的特例,Djikstraμ=(vv).-,(v,v) -.v,v.算法所采用的一“致代价搜索在人工智能中称为贪心搜索策略,它是初级的启三算法的特点与改进方法发性搜索策略。Diktra遍历计算的节点数目很多.所以需要的时间相对比较长,对于一一、算法思想些少节点的图尚可应用,对于-些节点数日非常多的网络閱就满要重复计算该算法的主要思想是,假设已经求出从v,到v,的最短路径μ "如下:很多次，显得非常麻烦.为此,我们可以考虑采取以下几点措施:在整个计算过程中,我们可以考虑做完第一步之后,去寻找最后一 -个节点根据最短路径的性质,从vs沿u "到v,或者v、的路,就是vs到v或者v。vt,看一下它的先行节点有哪些,然后,再返回到第一步的计算结果,来对比vt的最短路径。这就是说u "不仅是起点V,到终点v,的最短路，而且从起点v,的先行节点号是否跟得出的非无穷路径里的节点号有重复的。如果有,则提到终点v_上任意中间点的最短路也在对应节点的山'上。为了求得v,到v的取这--路径,作为- -个备选路径。然后按正常的第二步计算第二次迭代,在第最短路，可以先求出vs到每-一个中间点的最短路,然后逐步扩展到找终点V。二次迭代之后,继续对比v,的先行节点号是否跟得出的非无穷路径里的节点二、算法过程号有重复的。如果有，则提取这-路径,作为- -个备选路径。在计算过程中,需要将已经求出到起点最短路的点与尚未求出到起点最如此循环,- -直到vt的先行 节点全部找到为止,然后在这些备选路径里短路的点区别开来,以顺序执行选代。这个问题呵以用不同的标号来解决,即选择最短路径,同时也就知道了最短路径的中间节点。从vs开始,对每个顶点给以不同的标号.在这种算法中一般有两类标号:临这样计算可以减少很多计算步骤, 省略很多非先行节点。个人认为可以时标号Lj和永久标号dj, LJ表示从起点到被标号vj的最短路权的一个数值，适当的提高算法的效率。但不一定是最短的路径,dj表示从vs开始到被标号点vj的真正对短路权.具Dijksta算法在上述计算过程中可以找到起点到其他点的最短路径,同体步骤如下:时我们还可以在Dijkstra算法的基础上作-些扩展, 有时候，我们希望在求得1. k=1,d, (1) =0,L (1) =w。(j≠s)。N={v}最短路径的基础上还可以列出一些次短的路径,或者是找到路径的序列。为2.将各Ljk中数值最小者对应的顶点标号x的改成永久性标号,即:此,可先在原图上计算出最短路径,然后从图中删去该最短路径中的某-条Dxk)=min{L()}边,在余下的子图中重新计算最短路径。对于原每条最短路径中的每一条边，3.如果N={vy}则算法终止。d, x)就是从v,到v,的最短路的权。均可求得一条删去该边后f图的最短路径，,这些最短路径路径经排序后即为4.如果未能找到最终节点,则需要继续迭代,令k=k+1,对每一_个v,∈原图的一系列次短路径。N.的顶点由下述方法修改其标号:即对每一条弧(Vv,v)令:参考文献u (u) =min({Q(",dx (-1 +wj}(1]军.郭耀煌:《物流配送车辆调度理论与方法景,中国物资出版社。5.反向追踪[2]郭耀煌: 《运筹学原理与方法》,西南交通大学出版社.从最后顶点vt开始反向寻找,先看终点t的先行节点中是否存在一点作者简介-点vj使满足1.冯翠杰(1983一),女,山东潍坊人,烟台南山学院教师,硬士,主要研d+w,=d,究方向:工程测量，工程管理. .如果有,则记下有向边(v,v)然后再从vj开始寻求它的先行节点vi使:2.孙晓琳。(1982-),女山东烟台,助教,工学硕士.(接上页)图像分割是图像分析的重要环节,也是计算机视觉的重要研究方[1]杨润玲, 高新流,介军.一种基于模糊聚类的快速图像分割算法[J].面。本文在对模糊C均值紧类算法和区城生长算法进行分析的基础上,提出了西安建筑科技大学学报:自然科学版, 2007, 39 (2): 280-285.-种将模糊C均值聚类 算法与区域生长算法相结合的混合分割方法。该算法[2] BEZDEKJ C.Paltern recognition with objective function能够有效地提高分割区城的完整性.实验结果表明该方法能够取得好的分割algorithms (w]. New York: Plenun Press, 1981.效果。[3] wAN SY.HIGGINS v. Symetric region growing []. IEEB Trans-标准的区域生长算法要依赖于用户进行交互输入,需要根据生长结果不actions on Imare Process ing.2003. 12 (9): 1007.断地对闢值参数进行调整,阔值过大可能导致过生长,國值过小则叮能导致生中国煤化工图像的分制([D].兰州:兰州长不完全。模糊C均值檠类算法同样需要用户交互输人,以确定合理的聚类中心数。本文算法则是预先给定阈值参数进行区城生长,随后根据区城生长YHc N M H G欺群聚类的图像分制()]. .确定的区域敷用模糊C均值聚类算法作后续的分割处理,使分割取得了较好算机应用研究, 2008, 25 (5): 1579-1581.的结果。[6] RAFAEL C. Gonzalez, RICHARD E. Nwoods. 数字田像处理(MATLAB版)0].阮秋琦等,译.北京:电子工业出版社，2005.94序黢穗务2011.03