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

摘要：

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

关键词：最短路径、迪杰斯特拉算法、优化研究、链表

所属期刊栏目：3

分类号：TP312(计算技术、计算机技术)

在线出版日期：2008-11-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：1702-1703,1734