Dijkstra算法的时间复杂度是什么？

Question

Dijkstra((V, E)):
  S = {}    //O(1)
  for each vertex v ∈ V:    //O(V)
    d[v] = ∞    //O(1)
  d[source] = 0    //O(1)
  while S != V:    //O(V)
    v = non visited vertex with the smallest d[v]    //O(V)
    for each edge (v, u):    //O(E)
      if u ∈/ S and d[v] + w(v, u) < d[u]:
        d[u] = d[v] + w(v, u)
    S = S ∪ {v}

注意: ∈/ 表示不在，我无法在代码中输入它。

这个问题可能与一些帖子重复。 理解Dijkstra算法的时间复杂度计算 Dijkstra算法的复杂度 Dijkstra算法中的复杂度 我阅读了它们，甚至看了一些Quora上的帖子，但仍然无法理解。我在伪代码中添加了一些注释并尝试解决它。我真的很困惑为什么它是O(E log V)。

- user8314628

Answer 1

“具有最小d[v]的未访问顶点”如果使用min heap，则实际上是O(1)，并且在最小堆中插入是O(log V)。

因此，对于其他循环，复杂度如您正确提到的一样：

  O((V logV) + (E logV)) = O(E logV) // Assuming E > V which is reasonable

- hbejgel

---

+1，很好的回答。为什么“假设E>V是合理的”？这是合理的吗？ - user5920478

边数少于顶点数的图将具有不连通的组件，这些组件可以在算法的目的下被忽略。 - hbejgel

Answer 2

对于一般图，时间复杂度为O((V logV) + (E logV)) = O(logV * (V + E))。

你不应该假设图是密集的，即|E| = O(|V|^2)，因为大多数应用中的图实际上是稀疏的，即|E| = O(|V|)。

- timtody