两者都可用于从单一来源寻找最短路径。 BFS 在 O(E+V)
中运行,而 Dijkstra 在 O((V+E)*log(V))
中运行。
另外,我看到 Dijkstra 在路由协议(protocol)中的使用很像。
因此,如果 BFS 可以更快地完成同样的事情,为什么还要使用 Dijkstra 算法?
最佳答案
Dijkstra 允许为每一步分配 1 以外的距离。例如,在路由中,可以根据速度、成本、偏好等分配距离(或权重)。然后,该算法会为您提供从源到遍历图中每个节点的最短路径。
同时,BFS 基本上只是在每次迭代时将搜索扩展一个“步骤”(链接、边缘,无论您在应用程序中如何调用它),这恰好具有找到最小 步骤数的效果 它需要从您的源(“根”)到达任何给定节点。
关于algorithm - 如果广度优先搜索 (BFS) 可以更快地完成同样的事情,为什么还要使用 Dijkstra 算法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3818079/