algorithm - Dijkstra 算法在排序列表/数组实现的优先级队列上的运行时间

Question

所以我很想知道该算法在排序列表/数组实现的优先级队列上的运行时间。我知道对于未排序的列表/数组，它是 O((n^2+m)) ，其中 n 是顶点数，m 是边数。因此，这相当于 O(n^2) 时间。但是如果我使用排序列表/数组会更快吗...运行时间是多少？我知道 extractmin 将是常数时间。

Answer 1

好吧，让我们回顾一下我们需要的dijkstra算法(为了以后引用，通常顶点和边被用作V和E，例如O(VlogE)):
将所有排序的邻接表合并在一起:O(E)
提取最小值: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)