algorithm - 如果广度优先搜索 (BFS) 可以更快地完成同样的事情，为什么还要使用 Dijkstra 算法？

Question

两者都可用于从单一来源寻找最短路径。 BFS 在 O(E+V) 中运行，而 Dijkstra 在 O((V+E)*log(V)) 中运行。

另外，我看到 Dijkstra 在路由协议(protocol)中的使用很像。

因此，如果 BFS 可以更快地完成同样的事情，为什么还要使用 Dijkstra 算法？

Answer 1

Dijkstra 允许为每一步分配 1 以外的距离。例如，在路由中，可以根据速度、成本、偏好等分配距离(或权重)。然后，该算法会为您提供从源到遍历图中每个节点的最短路径。

同时，BFS 基本上只是在每次迭代时将搜索扩展一个“步骤”(链接、边缘，无论您在应用程序中如何调用它)，这恰好具有找到最小 步骤数的效果 它需要从您的源(“根”)到达任何给定节点。