基于并行计算的快速Dijkstra算法研究

• 作者: 叶颖诗 蔡贤资 魏福义
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: Dijkstra算法 并行计算 最短路径 正则树 时间复杂度 仿真实验
• 年，卷（期）: 2020,（6）
• 所属期刊栏目: 理论与研发
• 页码范围: 58-65
• 页数: 8页
• 分类号: TP312
• 字数: 6523字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.1903-0119

摘要

通过分析经典Dijkstra算法的思想和执行流程,对多标号的Dijkstra算法给出新证明,以此作为理论依据对Dijkstra算法进行了多标号的串行与并行优化.对于正则树,给出了经典Dijkstra算法、串行多标号Dijkstra算法和并行多标号Dijkstra算法的时间复杂度排序.针对优化算法的特点,设计出四种实验,采用运行时间和并行加速比作为优化指标,考核三种算法的效率.仿真实验表明:对顶点数大于6000的稠密图和稀疏图(正则树),多标号并行算法优于串行算法,且优化效果明显;对于正则树,优化效果分别与深度、出度成正相关.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	蔡贤资	华南农业大学数学与信息学院	16	36	4.0	5.0
2	魏福义	华南农业大学数学与信息学院	20	48	3.0	6.0
3	叶颖诗	华南农业大学数学与信息学院	3	0	0.0	0.0