Computer Science ›› 2014, Vol. 41 ›› Issue (6): 217-224.doi: 10.11896/j.issn.1002-137X.2014.06.043

Previous Articles     Next Articles

Multi-adjacent-vertexes and Multi-shortest-paths Problem of Dijkstra Algorithm

WANG Shu-xi and LI An-yu   

  • Online:2018-11-14 Published:2018-11-14

Abstract: Dijkstra Algorithm is one of the most classical algorithms to solve the shortest path problem.This paper listed and analyzed Dijkstra Algorithm and its pseudo-code.To deeply understand Dijkstra Algorithm,listed several error views and rectified them.Through analyzing Dijkstra Algorithm,there are maybe multiple pre-adjacent vertexes for a vertex in one shortest path,and there are maybe multiple shortest paths with the same weight.Regrettably,Dijkstra Algorithm does not solve the above problems.To solve the above problems and improve Dijkstra Algorithm,we analyzed its causes,proposed an algorithm,gave its pseudo-code and programmed with c language,and analyzed the time complexity of this algorithm.Experimental results show that the improved Dijkstra algorithm can effectively solve the problem of multi-adjacent-vertexes and multi-shortest paths.

Key words: Dijkstra algorithm,Multiple pre-adjacent vertexes,Multiple shortest paths,Time complexity

[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!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!