基于OpenMP的Dijkstra算法并行优化研究  

作　　者：侯竞夫 

机构地区：[1]University of Nottingham

出　　处：《中国科技信息》2022年第11期110-111,共2页China Science and Technology Information

摘　　要：1959年,计算机科学家E.W.Dijkstra提出了Dijkstra算法。Dijkstra算法是一种解决单源最短路径问题的贪心算法,其作用主要表现在解决有向图中的最短路径问题方面。但随着科学技术的发展,Dijkstra算法的应用领域得到了极大的扩展,“最短路径”也被赋予了全新的含义,不再单单指空间中的最短距离,同样也可以用来研究各种时间、经济、能量消耗问题。但是,随着研究问题的复杂化以及所研究数据规模的逐渐扩大,传统的串行Dijkstra算法计算量大、时间复杂度较高的问题也逐渐体现出来,影响着Dijkstra算法在诸多问题中的表现。而并行化计算不仅在计算大规模数据时表现优异,也非常契合Dijkstra算法的算法思想。

关 键 词：DIJKSTRA算法 单源最短路径 贪心算法 大规模数据 数据规模 并行优化 最短距离 计算机科学家 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]