一种基于桶结构的单源最短路径算法

A Single-Source Shortest Path Algorithm Based on the Bucket Structure

以单源最短路径为主的最优路径问题是众多社会应用领域内选择最优问题的基础。本文分析了不同实现技术求解单源最短路径问题的算法,结合基于标记设定的Dijkstra算法和基于标记修正的BFM算法的思想,提出了一种基于桶结构的单源最短路径算法。实验结果表明,该算法与前两种算法相比,具有好的运行时间复杂度和可并行性。

The single-source shortest path problem as to the main optimal routing problem is the basis of the most optimal problems in many social application areas.This paper discusses the different single-source shortest path serial algorithms in term of the implementation technique,combining the ideas of the Dijkstra algorithm based on label setting and the BFM algorithm based on label correcting,a new kind of single-source shortest path algorithm based on the bucket structure is proposed.The experiments show that the proposed algorithm has good time complexity and parallelism property compared with the two former algorithms.