基于链表的Dijkstra算法优化研究

迪杰斯特拉算法是图论中计算最短路径的经典算法,但在实际使用中该算法耗费大量的计算时间和存储空间。通过对传统迪杰斯特拉算法的深入分析,在计算时间和存储空间上对该算法提出了一种新的优化方案,并给出了优化后的详细算法。改进算法从消除冗余计算和冗余存储入手,采用链表数组作为存储结构。经算法复杂度分析,优化后的迪杰斯特拉算法在求解最短路径问题时在时间和空间复杂度上都有明显的提高。该优化算法操作性强,具有一定的实用价值。

Optimization Research for Dijkstra Algorithm Based on Linked List

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.