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算法的时间复杂度计算 Dijkstra算法的复杂度 Dijkstra算法中的复杂度 我阅读了它们,甚至看了一些Quora上的帖子,但仍然无法理解。我在伪代码中添加了一些注释并尝试解决它。我真的很困惑为什么它是O(E log V)。