一种基于Dijkstra并行线程算法的研究与实现

Research and Implementation of One Parallel Thread Algorithm Based on Dijkstra

针对传统Dijkstra算法运行效率的问题,提出了一种基于传统Dijkstra并行线程的算法,该算法动态地将交通网络进行子网分割。通过实验测试了不同网络节点数量和弧段数量下传统Dijkstra算法和本文算法运行时间,实验结果表明本文算法能够缩减网络节点搜索空间,降低算法的时间复杂度,提高算法的运行效率。

Aiming at the problem of operating efficiency of traditional Dijkstra algorithm, the paper comes up with one algorithm of parallel thread based on traditional Dijkstra. The algorithm divises traffic network into subnets dynamically. Through experiment, the operating time of traditional Dijkstra algorithm is tested under different number of network junctions and arcs. The experiment has demonstrated that the algorithm can lower searching space of network junctions, reduce Dijkstra time complexity and improve Dijkstra operating efficiency.