我知道Dijkstra算法的步长顺序是这样的:
- 初始化arr
min_distance，将source设置为0，其他设置为MAX_VALUE - 选择不在
visited集合 中的最小距离 - 将顶点放到
visited集合 - 循环连接到不在
visitedset 中的选定顶点的所有边 - 更新所有最小距离
- 一直这样做，直到我们得到目标顶点或没有其他顶点可以选择
到目前为止，我已经看到了两种类型的实现，一种使用最小堆O(log V)来获得最小顶点，另一种使用简单的循环(O(V))。
我的问题是，如果我们使用最小堆，它说时间复杂度将是O(E log V) E可以写成V^2。没有它，我们可以得到O(V^2)的时间复杂度。为什么使用最小堆时时间复杂度看起来更糟?
对于普通二进制堆，更差。但前提是边的数量足够大。这就是为什么维基百科上写着:为什么使用最小堆时时间复杂度似乎更差?
For稀疏图Dijkstra的算法可以通过将图以邻接表的形式存储并使用[…]一个优先级队列来实现有效地提取最小值。
当使用可以提供O(1)个减键操作的堆时，也可以将时间复杂度保持在O(|V|²)，例如斐波那契堆。再次引用同一篇文章:
对于自平衡二叉搜索树或二叉堆，算法要求
Θ(V (E | | + | |)日志V | |)
时间在最坏的情况下[…];对于连通图，这个时间界限可以简化为Θ(|E|log|V|)。斐波那契堆将其改进为
Θ(E | | + | V日志| | |)
…当|E| = O(|V|²)= Θ(|V|²)