将 BFS 用于加权图

Question

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

我想知道 reason/explanation 为什么它不能用于加权图。是由于边缘的重量还是其他原因？有人能解释一下吗，我有点困惑。

PS：我完成了 this question and this 个问题。

Answer 1

考虑这样的图表：

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

从A到B的最短路径是经过C（总权重为2）。一个正常的 BFS 会直接从 A 到 B 的路径，标记 B 为已见，从 A 到 C，标记为 C。

下一阶段，从C开始传播，B已经标记为seen，所以从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 在移动到其他节点之前会考虑来自单个节点的 all 条边，而 Dijkstra 的算法将始终考虑最低权重 unseen条边，来自连接到目前为止见过的所有节点的边集。听起来很费解，但是伪代码很简单：

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 个权重为 1 的边和 n-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可以考虑这个算法，但是一般来说这个算法可能没有这么好的表现。

Answer 3

the teacher mentions that BFS/DFS can't be used directly for finding shortest paths in a weighted graph

对于初学者来说，DFS 不在 table 范围内并且根本不适用于最短路径。

其次， correctly explains why BFS fails on weighted graphs with cycles and suggests Dijkstra's，用优先级队列替换队列，并在找到到节点的新的更短路径时允许放宽。

但是，没有提到在加权有向无环图（加权 DAG）上，Dijkstra 的杀伤力太大了，单源最短路径可以在 O(|V|+|E|) 时间内找到按拓扑顺序松弛每个顶点。这种方法也适用于具有负权重边的 DAG。

高级算法如下：

distances = {V: infinity for V in vertices}
predecessors = {V: None for V in vertices}

for U in topological_sort(vertices):
    for V in adjacencies(U):
        if distances[V] > distances[U] + edge_weight(U, V): # relax the edge
            distances[V] = distances[U] + edge_weight(U, V)
            predecessors[V] = U

来源：

将 BFS 用于加权图

Using BFS for Weighted Graphs

algorithm

graph

breadth-first-search

shortest-path