如果广度优先搜索(BFS)可以更快地做同样的事情,为什么要使用Dijkstra的算法？

Question

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

另外,我见过Dijkstra在路由协议中使用了很多.

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

Answer 1

Dijkstra允许为每个步骤分配1以外的距离.例如,在路由中,距离(或权重)可以通过速度,成本,偏好等来分配.然后,算法为您提供从源到遍历图中的每个节点的最短路径.

同时BFS基本上只是在每次迭代时通过一个"步骤"(链接,边缘,无论你想在应用程序中调用它)扩展搜索,这恰好具有找到任何步骤所需的最小步骤数的效果.来自您的源("root")的给定节点.

Answer 2

如果您考虑旅行网站,由于节点上的权重(距离),这些使用Dijkstra的算法.

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

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

在这里,如果我们应用BFS,答案将是ABF或ACF,因为两者都是最短路径(相对于边数),但如果我们应用Dijstra,答案将仅为ABF,因为它考虑了连接上的权重路径.

Answer 3

Dijkstra 算法

• 像用于加权图的 BFS。
• 如果所有成本都相等，Dijkstra = BFS

来源：https : //cs.stanford.edu/people/abise/gs.pdf

Answer 4

对此有一个困惑，可以使用修改的 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))

Answer 5

从实现角度来看，Dijkstra算法可以通过交换来实现酷似BFSqueue用priority queue。

来源