Multi-adjacent-vertexes and Multi-shortest-paths Problem of Dijkstra Algorithm
Wang Shu-x · 2014
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.