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

摘要

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