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 算法的时间复杂度计算

Complexity in Dijkstras algorithm

我看了他们甚至Quora上的一些帖子，但仍然无法理解。我在伪代码中添加了一些注释并尝试解决它。我真的很困惑为什么它是 O(E log V)

Answer 1

如果您使用 min heap 并且在最小堆中插入是 O(log V)，则 "non visited vertex with the smallest d[v]" 实际上是 O(1)。

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

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

Answer 2

一般图是O((V logV) + (E logV)) = O(logV * (V + E))。

你不会只是假设图是稠密的，即 |E| = O(|V|^2) 因为应用程序中的大多数图实际上是稀疏的，即 |E| = O(|V|).

Dijkstra算法的时间复杂度是多少

What's the time complexity of Dijkstra's Algorithm

dijkstra

time-complexity