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

Question

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

\n\n

注意：\xe2\x88\x88/ 表示不在，我无法在代码中键入它。

\n\n

这个问题可能与某些帖子重复。

\n\n

了解 Dijkstra 算法的时间复杂度计算\n

\n\n

Dijkstra 算法的复杂性

\n\n

Dijkstras 算法的复杂性

\n\n

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

\n

Answer 1

如果您使用最小堆并且在最小堆中插入的时间复杂度为 O(log V)，那么“具有最小 d[v] 的未访问顶点”实际上是 O(1) 。

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

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