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 算法的时间复杂度计算 https://stackoverflow.com/questions/26547816/understanding-time-complexity-calculation-for-dijkstra-algorithm
Dijkstra 算法的复杂性 https://stackoverflow.com/questions/38772780/complexity-of-dijkstras-algorithm
Dijkstra 算法的复杂性 https://stackoverflow.com/questions/26328860/complexity-in-dijkstras-algorithm
我读过它们,甚至读了 Quora 上的一些帖子,但仍然无法理解。我在伪代码中添加了一些注释并尝试解决它。我真的很困惑为什么它是 O(E log V)
如果您使用a,“具有最小d[v]的未访问顶点”实际上是O(1)min heap https://en.wikipedia.org/wiki/Binary_heap插入最小堆的时间复杂度为 O(log V)。
因此,复杂性正如您对其他循环正确提到的那样:
O((V logV) + (E logV)) = O(E logV) // Assuming E > V which is reasonable
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)