计算机科学 ›› 2014, Vol. 41 ›› Issue (6): 217-224.doi: 10.11896/j.issn.1002-137X.2014.06.043
王树西,李安渝
WANG Shu-xi and LI An-yu
摘要： Dijkstra算法是图论中求取最短路径的经典算法。列举并分析了Dijkstra算法及其伪码,为了深刻理解Dijkstra算法,列举了几种错误观点并加以纠正。分析发现,根据Dijkstra算法,最短路径上的某个顶点的前面,可能有多个邻接点；从开始点到某个顶点之间,可能存在多条权重相同的最短路径。对于上述多邻接点问题与多条最短路径问题,Dijkstra算法并没有涉及。分析了多邻接点问题与多条最短路径问题的成因,提出解决方案,对Dijkstra算法进行了改进,给出了改进之后的算法与伪码,分析了算法的时间复杂度,并用c语言编码实现。实验结果表明,改进之后的Dijkstra算法可以有效解决多邻接点问题与多条最短路径问题。
| [1] Dijkstra E W.A note on two problems in connexion with graphs[J]．Numberische Mathematik,1959,1(1):269-271 [2] 王树西,吴政学.改进的Dijkstra最短路径算法及其应用研究[J].计算机科学,2012,39(5):151-153 [3] 董俊,黄传河.改进Dijkstra算法在GIS导航应用中最短路径搜索研究[J].计算机科学,2012,39(10):125-130 [4] 刘国华.基于Dijkstra距离的聚类算法研究及其在物流中的应用[D].兰州:兰州大学,2011 [5] 郑四发,曹剑东,连小珉.复杂路网下多客户间最短路径的扇面Dijkstra算法[J].清华大学学报:自然科学版,2009(11):115-120 [6] 刘建美,马寿峰,马帅奇.基于改进的Dijkstra算法的动态最短路计算方法[J].系统工程理论与实践,2011(6):200-206 [7] 李敬贤,厉小润.求解震后最优路径的改进Dijkstra算法[J].计算机工程,2012(3):177-183 [8] 周竞文,程志全,金士尧.基于Dijkstra距离剪枝的测地线求解算法[J].系统仿真学报,2009(10):92-98 [9] 吴若伟,楼佩煌.基于Dijkstra算法的大型停车场最优泊车路径规划[J].工业控制计算机,2013(5):183-189 [10] Idwan S,Etaiwi W．Dijkstra algorithm heuristic approach for large graph[J]．J Appl Sci,2011,12:2255-2259 [11] Medeiros F L L,da Silva J D S．A Dijkstra Algorithm for Fixed-Wing UAV Motion Planning Based on Terrain Elevation[J]．Lecture notes in computer science,2010,6404:213-222 [12] Gunkel C,Stepper A,Muller A C ,et al.Micro crack detection with Dijkstra’s shortest path algorithm[J]．Machine Vision and Applications,2012,23(3):589-601 [13] Li R．Utilizing Restricted Direction Strategy and Binary HeapTechnology to Optimize Dijkstra Algorithm in WebGIS[J]．Key Engineering Materials,2010(419/420):557-560 [14] Tintor V,Radunovi A J．Distributed Dijkstra sparse placementrouting algorithm for translucent optical networks[J]．Photonic Network Communication,2009,18(1):55-64 [15] Kimoto M,Tsuchiya T,Kikuno T．On the Time Complexity of Dijkstra’s Three-State Mutual Exclusion Algorithm[J]．IEICE Transactions on Information and Systems,2009,92(8):1570-1573 [16] Bauer R,Delling D,Sanders P,et al.Combining Hierarchical and Goal-Directed Speed-Up Techniques for Dijkstra’s Algorithm[J]．Lecture Notes in Computer Science,2008,5038:303-318 [17] 耿素云．离散数学[M]．北京:清华大学出版社,2008 [18] 吕建华,王国仁,于戈.XML数据的路径表达式查询优化技术[J].软件学报,2003(9):1193-1199 [19] 孔令波,唐世渭,杨冬青,等.XML数据的查询技术[J].软件学报,2007(6):1400-1418 [20] 孟小峰,王宇,王小锋．XML查询优化研究[J].软件学报,2006(10):2069-2086 [21] 孔令波,唐世渭,杨冬青,等．XML数据索引技术[J].软件学报,2005(12):1000-1017 |
| No related articles found! |
|
||
首页