单源点最短路径动态优化算法

摘要：

设计了最短路径时间复杂度取决于边数e和点数n的动态优化算法.采用了独特的动态PV集合链,改进了当前求得的最短路径向量D的存储结构,用PV集合链对向量D进行动态管理,使其时间开销为e+(n-1)×(n-2)/2+3n.当n＞4时,SPDOA算法的性能明显优于Dijkstra算法,呈现出良好的动态优化特性.最后对动态优化算法与Dijkstra算法用理论公式得出的数据进行了时间性能比较.

关键词：Dijkstra、最短路径、动态优化算法、PV集合

所属期刊栏目：42

分类号：TP301.6(计算技术、计算机技术)

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

页数：共4页

页码：82-85