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

• 作者: 张吉赞 李洪波
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: Dijkstra 最短路径 动态优化算法 PV集合
• 年，卷（期）: 2006,（3）
• 所属期刊栏目: 学术探讨
• 页码范围: 82-85
• 页数: 4页
• 分类号: TP301.6
• 字数: 5115字
• 语种: 中文
• DOI: 10.3321/j.issn:1002-8331.2006.03.025

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李洪波	烟台师范学院数学与信息学院	14	130	6.0	11.0
2	张吉赞	烟台师范学院数学与信息学院	6	21	3.0	4.0