Dijkstra算法复杂度与BFS复杂度

Question

我一直在练习各种算法，我刚刚完成了Dijkstra算法来计算图上节点之间的最短距离。在完成了利用索引minHeap的练习之后，我还完成了利用BFS (附带的解决方案)的练习。这让我想到了几个问题：

1. ，如果我对时间复杂度的计算是正确的-我计算了附加解的复杂性为O(v^2 + e)，其中V=顶点数，E=边数。我们迭代和触摸每个节点一次，而且只有一次，边缘也是一样。v^2来自shift操作，因为在每个iteration.
2. This BFS解决方案上都可以通过利用类似于Java中的ArrayDeque来改进这一点，这将给我们O(1)操作，每次我们跳出队列的前端，并且应该将我们的时间复杂度降低到O(v+e)
3. ，如果上述情况属实，那么利用Dijkstra的算法而不是BFS的优点或用例是什么？似乎BFS的时间复杂度(O(V+E))要比Dijkstra的O((V+E)*log(V))要好，并且可以防止负循环的情况，在这种情况下，Dijkstra的循环将陷入无限循环。

示例输入：

边=[1，7]，[2，6，3，20，4，3]，[3，14]，[4，2]，[]，[]

开始=0

​

​

Answer 1

BFS和Dijkstras算法计算两种不同的东西，它们在某些情况下是相同的。

给定起始节点s

edges.

• Dijkstras算法通过跳数计算到所有其他节点的最短路径/算法的数目根据边缘权重计算到所有其他节点的最短路径。

这是两种不同的东西，但在某些情况下它们是相同的。

图是一棵树(任何给定的节点之间只有一条路径)，所有的边权都是相等的(或者图是unweighted). )

如果使用Fibonacci堆实现Dijkstras算法的时间复杂度为O(用Fibonacci堆实现的话，时间复杂度为O(x=0)，而BFS的时间复杂度为O(x=0)。

因此，如果输入允许您在两者之间进行选择，BFS可能是一个很好的选择，这是正确的。然而，在实践中，您可能希望首先对真实世界的数据进行一些基准测试。