难道Dijkstra算法和Bellman Ford算法的时间复杂度不应分别为O(|V|^2)和O(|V|^3)吗？我一直在阅读here和here的伪代码。
Bellman Ford算法和Dijkstra算法看起来非常相似，除了Bellman Ford算法与Dijkstra的|V|时间算法（其中|V|是节点数）相同的过程。那么为什么我在这个主题上访问的每篇文章都说Dijkstra的算法在O(|v|^2)中运行，而Bellman Ford算法在O(|V||E|)时间复杂度上运行？我哪里出错了（如果我真的这么做的话）？
更新：你不觉得：|E| = (|V|^2 - |V|)/ 2如果每个节点都连接到彼此的节点？因此，我们假设每个节点都与每个其他节点连接。现在我们得到，O(|V|^3)为贝尔曼福特算法。我对吗？
所以我们有O(|V||E|) = O(|V|(|V|^2 - |V|)/2) = O(|V|^3)。是对的吗？如果没有，我哪里出错了？
Dijkstra算法和Bellman Ford算法的时间复杂度不应分别为O（| V | ^ 2）和O（| V | ^ 3）吗？
是（1），但这不会是一个严格的约束。同样地，你可以说它是O(|V|^5)，它也是正确的（回想一下，大O是渐近的上界，而不是一个紧的上界）。
许多图形不是密集的，而是稀疏的，并且连接到每个顶点的边缘的数量是亚线性的。所以，如果我们使用| E |符号也是如此，我们可以获得更好的更紧密（和更多信息）的界限。
类似地，考虑一个遍历大小为nxm的矩阵的算法。说这个算法是O(n*m)更有用，而不是说它是O(max{n,m}^2)，不是吗？
关于Dijkstra算法的实现，实际的复杂性在很大程度上取决于最小堆实现中的修改值，而有些实现可以在对数时间内完成（给出O(|E|+|V|log|V|)总时间，一些实现不打扰，只是去对于在O(|V|^2)中运行的更简单的解决方案。
（1）假设这里有简单的图形