文献类型：期刊文章

作　　者：叶颖诗[1] 魏福义[1] 蔡贤资[1]

YE Yingshi;WEI Fuyi;CAI Xianzi(College of Mathematics and Information,South China Agricultural University,Guangzhou 510000,China)

机构地区：[1]华南农业大学数学与信息学院

出　　处：《计算机工程与应用》

基　　金：广东省联合培养研究生示范基地人才培养项目;华南农业大学2018质量工程项目;广东省教育厅特色创新类项目（No.2017KTSCX020）

年　　份：2020

卷　　号：56

期　　号：6

起止页码：58-65

语　　种：中文

收录情况：AJ、BDHX、BDHX2017、CSA、CSA-PROQEUST、CSCD、CSCD_E2019_2020、IC、INSPEC、JST、RCCSE、ZGKJHX、核心刊

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

关 键 词：DIJKSTRA算法 并行计算 最短路径 正则树  时间复杂度 仿真实验  

分 类 号：TP312]