algorithm - 使用BFS加权图

我正在修改单源最短路径算法，在视频中，老师提到 BFS / DFS 不能直接用于在加权图中找到最短路径(我想每个人都已经知道这一点)，并说自己找出原因。

我想知道为什么它不能用于加权图的确切原因/解释。是由于边缘的重量还是其他原因？有人可以解释一下，因为我感到有些困惑。

PS:我遇到了this问题和this问题。

最佳答案

考虑这样的图:

A---(3)-----B
|           |
\-(1)-C--(1)/

从A到B的最短路径是通过C(总重量为2)。正常的BFS将直接采用从A到B的路径，如图所示标记为B，从A到C的标记路径为C。

在下一阶段，从C传播，B已标记为可见，因此从C到B的路径将不被视为潜在的较短路径，并且BFS会告诉您从A到B的最短路径具有权重的3。

您可以使用Dijkstra's algorithm代替BFS在加权图上找到最短路径。在功能上，该算法与BFS非常相似，并且可以通过与BFS类似的方式编写。唯一改变的是您考虑节点的顺序。

例如，在上图中，从A开始，BFS将处理A-> B，然后处理A-> C，并在那里停止，因为已经看到了所有节点。

另一方面，Dijkstra的算法将如下运行:

考虑A-> C(因为这是来自A的最低边缘权重)

考虑C-> B(因为这是到目前为止我们所到达的任何节点的最低权重边缘，因此我们尚未考虑)

考虑并忽略A-> B，因为已经看到了B。

注意，差异仅在于检查边缘的顺序。 BFS将考虑单个节点的所有边缘，然后再移动到其他节点，而Dijkstra的算法将始终考虑连接到的所有边缘中的最低权重看不见的边缘，到目前为止，所有已看到的节点。听起来令人困惑，但是伪代码非常简单:

create a heap or priority queue
place the starting node in the heap
dist[2...n] = {∞}
dist[1] = 0
while the heap contains items:
   vertex v = top of heap
   pop top of heap
   for each vertex u connected to v:
       if dist[u] > dist[v] + weight of v-->u:
           dist[u] = dist[v] + weight of edge v-->u
           place u on the heap with weight dist[u]

Wikipedia的此GIF可以很好地直观显示发生的情况:

请注意，这看起来与BFS代码非常相似，唯一的真正区别是使用堆(而不是常规队列数据结构)，该堆是按照与节点的距离排序的。