摘要
通过分析经典Dijkstra算法的思想和执行流程,对多标号的Dijkstra算法给出新证明,以此作为理论依据对Dijkstra算法进行了多标号的串行与并行优化。对于正则树,给出了经典Dijkstra算法、串行多标号Dijkstra算法和并行多标号Dijkstra算法的时间复杂度排序。针对优化算法的特点,设计出四种实验,采用运行时间和并行加速比作为优化指标,考核三种算法的效率。仿真实验表明:对顶点数大于6000的稠密图和稀疏图(正则树),多标号并行算法优于串行算法,且优化效果明显;对于正则树,优化效果分别与深度、出度成正相关。
In order to make optimized to Dijkstra algorithm,this paper gives a proof of multi-label Dijkstra algorithm and uses it as a fundamentals to make the optimized improvement,which is the classical Dijkstra algorithm and the multi-label Dijkstra algorithm with serial and parallel way.Facing the regular graph,this paper calculates three algorithm time complexity.After analysis,this paper comes up with multi-label parallel computing for the Dijkstra optimized algorithm.This optimized algorithm designs four experiment to verify degree of optimization by running time and parallel acceleration ratio.The experiment result shows the multi-label parallel computing algorithm is more effective than the classical Dijkstra algorithm and the multi-label serial computing algorithm facing the dense graph which point number are more than 6000 and sparse graph(regular tree).For the regular tree,it exists positive correlation between the effectiveness and regular tree’s depth and out degree.
作者
叶颖诗
魏福义
蔡贤资
YE Yingshi;WEI Fuyi;CAI Xianzi(College of Mathematics and Information,South China Agricultural University,Guangzhou 510000,China)
出处
《计算机工程与应用》
CSCD
北大核心
2020年第6期58-65,共8页
Computer Engineering and Applications
基金
广东省联合培养研究生示范基地人才培养项目
华南农业大学2018质量工程项目
广东省教育厅特色创新类项目（No.2017KTSCX020）
