Abstract:

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.

Key words: bucket structure;singlesource shortest path;Dijkstra algorithm;BFM algorithm