The Improved Algorithm about the Single Source Shortest Path Problem
Yulin Zhou · 2001
In this paper we investigate the under bound of the time complexity of the single source shortest path problem, we have improved the single source shortest path algorithm and given a new algorithm, which time-complexity is O(tn+m) or O(nlogt+m) while in the case of different priority queue. n=|V|, m=|E|, t is the number of the EXTRACT-MIN operation of priority queue, in this paper which we rely on Fibonacci heap and topological sort.