143

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

此外，我还看到 Dijkstra 在路由协议中的使用非常相似。

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

4

6 回答 6

190

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

同时，BFS 基本上只是在每次迭代时将搜索扩展一个“步骤”（链接、边缘，无论您想在应用程序中调用什么），这恰好具有找到到达任何位置所需的最少步数的效果。来自您的源（“根”）的给定节点。

于 2010-09-29T00:58:54.553 回答
30

如果您考虑旅游网站，由于节点上的权重（距离），这些网站使用 Dijkstra 算法。

如果您会考虑所有节点之间的距离相同，那么 BFS 是更好的选择。

例如，考虑A -> (B, C) -> (F)由A->B= 10, A->C= 20, B->F= C->F= 5 给出的边权重。

在这里，如果我们应用 BFS，答案将是 ABF 或 ACF，因为两者都是最短路径（相对于边的数量），但如果我们应用 Dijstra，答案将是 ABF，因为它考虑了连接的权重小路。

于 2013-08-10T11:19:14.683 回答
19

Dijkstra 算法

  • 就像加权图的 BFS 一样。
  • 如果所有成本都相等，则 Dijkstra = BFS

资料来源：https ://cs.stanford.edu/people/abisee/gs.pdf

于 2018-10-06T06:43:29.963 回答
6

从实现的角度来看，Dijkstra 的算法可以通过将queue与priority queue.

来源

于 2019-05-02T13:08:19.887 回答
3

对此存在混淆，可以使用修改后的 BFS 算法在加权有向图中找到最短路径：

  1. 使用优先队列而不是普通队列
  2. 不跟踪访问节点，而是跟踪与起始节点的距离

由于 2，一些节点将被访问一次以上，这使得它与 Dijkstra 相比效率较低。

shortest = sys.maxsize

queue = [(0, src, 0)]
while queue:
    (cost, node, hops) = heapq.heappop(queue)
    if node == dst:
        shortest = min(distance, cheapest)
    for (node_to, node_distance) in edges[node]:
        heapq.heappush(queue, (cost + node_distance, node_to, hops + 1))
于 2021-01-20T22:25:46.487 回答
0
  • BFS 仅在您将最短路径计算为步数边缘时起作用，或者任何应用程序为所有边缘分配相同（但为正）的权重。
  • BFS 和 Dijkstra 的区别只是将 FIFO 队列替换为优先级队列！

请注意，这并不能解决边缘上的正权重约束，Bellman-Ford 通过支付速度惩罚来解决一个著名的缺点 Dijkstra（和 BFS）

资料来源：Erickson, Jeff (2019) 第 8.4、8.6 章。算法

于 2021-11-26T02:37:00.493 回答