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

摘要：

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

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

所属期刊栏目：56

分类号：TP312(计算技术、计算机技术)

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

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

页数：共8页

页码：58-65