time-complexity - Dijkstra算法的时间复杂度是多少
问题描述
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}
注意: ∈/ 表示不在,我无法在代码中输入。
这个问题可能与某些帖子重复。
我阅读了它们,甚至在 Quora 上阅读了一些帖子,但仍然无法理解。我在伪代码中添加了一些注释并试图解决它。我真的很困惑为什么它是 O(E log V)
解决方案
如果您使用最小堆并且在最小堆中的插入是 O(log V),那么“具有最小 d[v] 的未访问顶点”实际上是 O(1 )。
因此,复杂性正如您为其他循环正确提到的那样:
O((V logV) + (E logV)) = O(E logV) // Assuming E > V which is reasonable
推荐阅读
- android - 使用 Android BLE Apache-Cordova 从 kCBAdvDataManufacturerData 中提取数据
- javascript - 从 iframe 访问 var 到父级
- css - 如何在带有 MacOS Mojave 的 CSS 中使用暗模式?
- python - 下载维基百科转储时出现 503 错误
- docker - minikube 0.30.0 DNS 在 CentOS 7 上无法使用 Docker 18.06.1-ce 和 vm-driver=none
- python - 如何使用 scikit learn 管道简化我的数据预处理
- javascript - 使用 Firebase 数据库的嵌套 Promise 函数
- javascript - 节点 Js mysql(和 mysql2) ECONNRESET
- javascript - 在 Node.js JavaScript 中确定是否安装了软件以及 Mac 上的版本
- android - 当应用程序崩溃时,Nativescript Sentry 没有获取用户数据