单源最短路径问题的改进算法  

The Improved Algorithm about the Single Source Shortest Path Problem

作　　者：周玉林[1] 

机构地区：[1]上饶师范学院数学与计算机系,江西上饶334001

出　　处：《上饶师范学院学报》2001年第3期18-22,共5页Journal of Shangrao Normal University

基　　金：上饶师院科研基金资助课题

摘　　要：探讨了单源最短路径问题算法所能达到的时间复杂性的下界 ,提出了时间复杂性为O(tn+m)和O(nlogt+m)的改进算法 ,其中n =|V|,m =|E|,t为从优先队列中抽取最小结点的次数 ,我们主要用Fibonacci堆和拓扑排序的思想方法。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.

关 键 词：单源最短路径 拓扑排序 Fibonacci堆 算法 优先队列 时间复杂性 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] O224[自动化与计算机技术—计算机科学与技术]