gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-04 07:15:18 32 4
gpt4 key购买 nike

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}

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

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

Understanding Time complexity calculation for Dijkstra Algorithm

Complexity Of Dijkstra's algorithm

Complexity in Dijkstras algorithm

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

最佳答案

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

因此,复杂性正如您在其他循环中正确提到的那样:

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

关于time-complexity - Dijkstra 算法的时间复杂度是多少,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53752022/

32 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com