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

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

另外，我看到 Dijkstra 在路由协议中使用了很多类似的东西。

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

68410 次浏览
小开
最佳答案

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

与此同时，BFS 基本上只是在每次迭代中将搜索扩展了一个“步骤”(链接、边缘，无论你想在应用程序中如何称呼它) ，这恰好产生了从源(“ root”)到任何给定节点所需的最小 步数的效果。

小开

如果你考虑旅游网站，这些使用 Dijkstra 的算法，因为权重(距离)的节点。

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

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

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

小开

Dijkstra 的算法

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

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

小开

从实现的角度来看，Dijkstra 的算法可以像 BFS 一样通过将 queue与 priority queue交换来实现。

来源

小开

这里有一个混淆，可以使用改进的 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))
小开
  • BFS 只有在您将最短路径计算为步骤边数，或者任何应用程序为所有边赋予相同(但为正)权重时才能工作。
  • BFS 和 Dijkstra 之间的区别仅仅是用优先级队列替换 FIFO 队列！

注意，这并不能修复边缘上的正权重约束，一个著名的缺点 Dijkstra (和 BFS)已经被 Bellman-Ford 通过支付速度惩罚修复了

来源: Erickson，Jeff (2019)8.4,8.6章，算法

小开

BFS 和 Dijkstra 都可以用来查找 最短的路径。如何定义最短路径的区别:

  • BFS: 边数最少的路径(假设每条边的权重相同或没有权重)。
  • Dijkstra: 路径上权重最小的路径。

考虑一下这个无向连通图:

enter image description here

我们想找到从 A到 F的最短路径:

  • BFS: A-> C-> E-> F 或 A-> B-> D-> F
  • 迪克斯特拉: A-> C-> E-> D-> F

实现非常类似，Dijkstra 的关键部分是优先级队列的使用:

    graph = {
'A': {('B', 2), ('C', 1)},
'B': {('A', 2), ('C', 4), ('D', 3)},
'C': {('A', 1), ('B', 4), ('E', 2)},
'E': {('C', 2), ('D', 1), ('F', 4)},
'D': {('B', 3), ('E', 1), ('F', 2)},
'F': {('D', 2), ('E', 4)}
    

}
    

    

def dijkstra(graph, start: str):
result_map = defaultdict(lambda: float('inf'))
result_map[start] = 0
    

visited = set()
    

queue = [(0, start)]
    

while queue:
weight, v = heapq.heappop(queue)
visited.add(v)
    

for u, w in graph[v]:
if u not in visited:
result_map[u] = min(w + weight, result_map[u])
heapq.heappush(queue, [w + weight, u])
    

return dict(result_map)
    

print(dijkstra(graph, 'A'))

产出:

{'A': 0, 'C': 1, 'B': 2, 'E': 3, 'D': 4, 'F': 6}

而对于 BFS，普通队列就足够了:

    graph = {
'A': {'B', 'C'},
'B': {'A', 'C', 'D'},
'C': {'A', 'B', 'E'},
'E': {'C', 'D', 'F'},
'D': {'B', 'E', 'F'},
'F': {'D', 'E'}
}
    

    

def bfs(graph, start: str):
result_map = defaultdict(int)
    

visited = set()
queue = deque([[start, 0]])
    

while queue:
v, depth = queue.popleft()
visited.add(v)
    

if v in graph:
result_map[v] = depth
    

for u in graph[v]:
if u not in visited:
queue.append([u, depth + 1])
visited.add(u)
    

return dict(result_map)
    

    

print(bfs(graph, 'A'))

产出:

{'A': 0, 'C': 1, 'B': 1, 'E': 2, 'D': 2, 'F': 3}

提交答案