使用 BFS 进行加权图

Question

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

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

PS：我经历了

this问题和this问题。

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 算法的运行方式如下：

考虑 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]

来自维基百科的这个 GIF 很好地可视化了所发生的情况：

请注意，这看起来与 BFS 代码非常相似，

唯一真正的区别是使用堆，按到节点的距离排序，而不是常规的队列数据结构

。

Answer 2

BFS/DFS

，只需对图中进行一些更改，如果您的图的权重是正整数，您可以将权重为

n

的边替换为权重为 1 的

n

边有

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

老师提到BFS/DFS不能直接用于在加权图中寻找最短路径

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

其次，

这个答案

正确解释了为什么 BFS 在带有循环的加权图上失败，并建议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

来源：

普林斯顿算法，4ed：4.4 最短路径
维基百科 - 拓扑排序：最短路径查找的应用

Answer 4

我们如何不获取访问数组。我们将能够采取最短路线 但什么时候停止就会陷入循环

以最便宜的航班为例，其中有 k 个停靠点。这里 bfs 用于获取最短路线，因为我们知道在这里我们不会乘坐超过 k 个停靠点，在某种程度上我们知道在这里停靠