Optimization Research for Dijkstra Algorithm Based on Linked List
Hongke Zhang · Computer Knowledge and Technology · 2008
Dijkstra algorithm is a classic algorithm for computing the shortest path,but it uses lots of time and memories in practice.On the basis of analyzing Dijkstra algorithm thoroughly,it shows a new optimal solution to the problem,and gives the detail algorithm.The improved algorithm can avoid redundant computing and storage,and uses linked list array as storage structure.The time complexity and space complexity of the algorithm are improved markedly in computing the shortest path.The improved algorithm with strong maneuverability could have important applications.