所以我很想知道算法的运行时间是由排序列表/数组实现的优先级队列.我知道对于未排序的列表/数组,它是O((n ^ 2 + m))其中n是顶点数,m是边数.因此,这相当于O(n ^ 2)时间.但如果我使用排序列表/数组会更快......运行时间是多少？我知道extractmin将是恒定的时间.
那么,让我们回顾一下dijkstra算法需要什么(为了将来参考,通常顶点和边用作V和E,例如O(VlogE)):
将所有排序的邻接列表合并在一起:O(E)
Extract Minimum:O (1)
减少密钥:O(V)
Dijkstra使用O(V)提取最小操作,O(E)减少密钥操作,因此:
O(1)*O(V)= O(V)
O(E)*O(V)= O(EV)= O(V ^ 2)
取最渐近重要的部分:
最终渐近运行时为O(V ^ 2).
这会变得更好吗？是.查看二进制堆,以及优先级队列的更好实现.
编辑:我实际上犯了一个错误,现在我又看了一遍.E不能高于V ^ 2,换句话说E = O(V ^ 2).
因此,在最坏的情况下,我们在O(EV)中运行的算法实际上是O(V ^ 2*V)== O(V ^ 3)