为什么 Dijkstra 最坏的时间复杂度在使用优先级队列时比不使用优先级队列时更差？
Why Dijkstra worst time complexity is worse using priority queue compared without using it?
我知道Dijkstra算法的步骤顺序是这样的：
- 初始化arr
min_distance，source为0，其他为MAX_VALUE
- 选择
visited集合中没有的最小距离
- 将顶点放入
visited 集合
- 遍历链接到不在
visited集合 中的选定顶点的所有边
- 更新所有的最小距离
- 继续这样做，直到我们获得目标顶点或无法选择其他顶点
到目前为止，我已经看到了 2 种类型的实现，一种使用最小堆 O(log V) 来获取最小顶点，另一种使用简单循环 (O(V))。
我的问题是，如果我们使用最小堆，它说时间复杂度将是O(E log V)，E可以写成V^2。如果没有它，我们可以获得 O(V^2) 时间复杂度。为什么使用最小堆时时间复杂度似乎更差？
Why does the time complexity seems worse when using min heap?
对于普通二进制堆，更糟。但前提是边的数量很大。这就是为什么 on Wikipedia 它说：
For sparse graphs, that is, graphs with far fewer than |V|² edges, Dijkstra's algorithm can be implemented more efficiently by storing the graph in the form of adjacency lists and using [...] a priority queue to implement extracting minimum efficiently.
当使用可以提供 O(1) decrease-key 操作的堆时，也可以将时间复杂度保持在 O(|V|²)，例如 Fibonacci堆。再次引用同一篇文章：
With a self-balancing binary search tree or binary heap, the algorithm requires
Θ((|E|+|V|)log|V|)
time in the worst case [...]; for connected graphs this time bound can be simplified to Θ(|E|log|V|). The Fibonacci heap improves this to
Θ(|E|+|V|log|V|)
...其中 -- 当 |E| = O(|V|²) -- 是 Θ(|V|²)
我知道Dijkstra算法的步骤顺序是这样的：
- 初始化arr
min_distance，source为0，其他为MAX_VALUE - 选择
visited集合中没有的最小距离 - 将顶点放入
visited集合 - 遍历链接到不在
visited集合 中的选定顶点的所有边
- 更新所有的最小距离
- 继续这样做，直到我们获得目标顶点或无法选择其他顶点
到目前为止，我已经看到了 2 种类型的实现，一种使用最小堆 O(log V) 来获取最小顶点，另一种使用简单循环 (O(V))。
我的问题是，如果我们使用最小堆，它说时间复杂度将是O(E log V)，E可以写成V^2。如果没有它，我们可以获得 O(V^2) 时间复杂度。为什么使用最小堆时时间复杂度似乎更差？
Why does the time complexity seems worse when using min heap?
对于普通二进制堆，更糟。但前提是边的数量很大。这就是为什么 on Wikipedia 它说：
For sparse graphs, that is, graphs with far fewer than |V|² edges, Dijkstra's algorithm can be implemented more efficiently by storing the graph in the form of adjacency lists and using [...] a priority queue to implement extracting minimum efficiently.
当使用可以提供 O(1) decrease-key 操作的堆时，也可以将时间复杂度保持在 O(|V|²)，例如 Fibonacci堆。再次引用同一篇文章：
With a self-balancing binary search tree or binary heap, the algorithm requires
Θ((|E|+|V|)log|V|)
time in the worst case [...]; for connected graphs this time bound can be simplified to Θ(|E|log|V|). The Fibonacci heap improves this to
Θ(|E|+|V|log|V|)
...其中 -- 当 |E| = O(|V|²) -- 是 Θ(|V|²)