使用BFS加权图

Question

我正在修改单源最短路径算法,在视频中,老师提到BFS/DFS不能直接用于在加权图中找到最短路径(我想每个人都已经知道了),并说明了解决原因的原因.你自己.

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

PS:我经历了这个问题和这个问题.

Answer 1

考虑这样的图:

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算法而不是BFS来查找加权图上的最短路径.在功能上,该算法与BFS非常相似,并且可以以与BFS类似的方式编写.唯一改变的是您考虑节点的顺序.

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

另一方面,Dijkstra的算法将按如下方式运行:

1. 考虑A - > C(因为这是来自A的最低边缘权重)
2. 考虑C - > B(因为这是我们到目前为止已达到的任何节点的最低权重边缘,我们还没有考虑过)
3. 考虑并忽略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]

来自维基百科的这个GIF提供了一个很好的可视化:

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

Answer 2

虽然这是事实，但你可以使用BFS/DFS加权的图形，在图形中的变化不大，如果你图的权重是正整数，你可以用重量代替边缘n与n边缘与重量1n-1中间节点。像这样的东西：

A-(4)-B

将会：

A-(1)-M1-(1)-M2-(1)-M3-(1)-B

并且不要在最终的 BFS/DFS 结果中考虑这些中间节点（如 M1,M2,M3 ）。

这个算法的复杂度是 O(V * M) 并且 M 是我们边的最大权重，如果我们知道在我们的特定图中M<log V可以考虑这个算法，但通常这个算法可能没有这么好的性能。