为什么Dijkstras算法的时间复杂度O（V ^ 2）

Question

我刚刚阅读了Wikipedia中有关Dijkstras算法的文章，其中说时间复杂度为O(V^2)。我的问题是我无法向自己解释。

有人可以向我解释吗？

Answer 1

使用数组的O(V^2)解决方案与“常规”（优先级队列）解决方案相同，但是使用具有开放距离的数组，而不是在堆中查找而不是进行堆查找。

open_nodes = [inf, inf, inf, ..., inf]
d = [inf, inf, inf, ..., inf]
open_nodes[source] = 0
while d[target] == inf:
  v = argmin(open_nodes)  // O(V)
  d[v] = open_nodes[v]
  for each u such that (v,u) is an edge:
    if d[u] != inf:
      // relaxation:
      open_nodes[u] = min(open_nodes[u], d[v] + w(v,u))
    // close v
  open_nodes[v] = inf

• 由于关闭节点，循环最多重复|V|次每次迭代，都不要重新打开它。
• argmin是O(|V|)。这基本上是在未排序的数组中找到最小值。
• 松弛采用O（1），并最多重复O(|E|)次，因为您为每个出局边最多调用一次。

这给我们总计O(|V|^2 + |E|)，但是由于|E| <= |V|^2，所以这只是O(|V|^2)