Dijkstra 最短路径算法优化.doc.doc

文档下载免费文档下载/ 本文档下载自文档下载网,内容可能不完整,您可以点击以下网址继续阅读或下载: /b5a0c60db880936cf95be3c7 Dijkstra 最短路径算法优化 Dijkstra 最短路径算法,非常适合相关专业的学生。第25卷第 3期2006 年8月文章编号:1006-4869(2006)03-0030-04 南昌工程学院学报 Dijkstra 最短路径算法优化章永龙(扬州大学信息工程学院,江苏扬州 225009) 摘??要: 传统 Dijkstra 算法在求解节点间最短路径时, 对已标识节点以外的大量节点进行了计算, 从而影响了算法的速度. 在对传统 Dijkstra 算法分析的基础上, 对其进行了优化, 优化算法只对最短路径上节点的邻居做了处理, 而不涉及到其他节点. 因此, 在优化算法中计算的节点数大幅减少, 提高了算法的速度. 关键词: 最短路径;Dijkstra 算法; 优化中图分类号: 文献标识码:A 文档下载免费文档下载/ OptimizationofDijkstraAlgorithm ZHANGYong-long (CollegeofInformationEnginneering,UniversityofYangzhou,Yangzhou225009,China)Abst ract:WhenashortestpathbetweennodesissearchedwithDijkstraalgorithm,alotofnodesawa yfromlaggednodesareinvolved, zationalgo- senodesthattheneigh-borofnodesintheshortestpathareprocessed,andothernodesaren??t ,/doc/b5a0c60db880936cf95be3c7timizationalgorithm,andefficiencyofth eoptimizationa-lgorithmisimproved. Keywords:theshortestpath;Dijkstraalgorithm;optimization 0?? 引??言实际生活中的许多问题都可归结于图论中的最短路径问题,如: 电子导航、交通旅游、公交出行等. 这里的最短路径不仅仅指地理意义上的距离最短, 可引申为最少费用、最短时间、延时最短、,如Dijkstra 算法 2[1] 用来求解图上从任一节点(源点) O(N); 采用邻接矩阵存储网络拓扑结构, 需要(N??N) 的存储空间, 随着节点数 N 的增大,其文档下载免费文档下载/ [2-5] ,提出了Dijkstr a算法的改进,本文在对传统Dijkstr a 算法分析的基础上, 对其进行了优化, 优化算法只对最短路径上节点的邻居做处理, ?? 传统 Dijkstra a算法是经典的解决最短路径问题的算法,它可以找出指定节点到其他各个节点间的最短路径,其主要思想是首先从收稿日期:2006-05-24 作者简介:章永龙(1976-), 男,江西高安人,助教,硕士. 第3期章永龙:Dijkstra 最短路径算法优化 31 源点求出长度最短的一条路径, ;;T是未标识集合; j是节点i到节点j的距离(i与j直接相连,否则 dij=??). 算法步骤如下 Step0:S=s;T=/b5a0c60db880936cf95be3c7M-S;wj=dsj(j?? T,s 与j直接相连)或wj=??(j??T,s 与j不直接相连). Step1: 在T中找到节点i,使s到i的距离最小,并将i划归到S.( 可从与s直接相连的j中考虑)若dsi=mindsj?? j与s直接相连,则将i划归到S中,即S=s,i,T=T-i;pi=s