对加权图使用 BFS [英] Using BFS for Weighted Graphs

问题描述

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

I was revising single source shortest path algorithms and in the video, the teacher mentions that BFS/DFS can't be used directly for finding shortest paths in a weighted graph (I guess everyone knows this already) and said to work out the reason on your own.

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

I was wondering the exact reason/explanation as to why it can't be used for weighted graphs. Is it due to the weights of the edges or anything else ? Can someone explain me as I feel a little confused.

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

PS: I went through this question and this question.

推荐答案

考虑这样的图表:

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

从 A 到 B 的最短路径是通过 C(总权重为 2).一个普通的 BFS 会直接走从 A 到 B 的路径，将 B 标记为可见，从 A 到 C，将 C 标记为可见.

The shortest path from A to B is via C (with a total weight of 2). A normal BFS will take the path directly from A to B, marking B as seen, and A to C, marking C as seen.

在下一阶段，从C传播，B已经被标记为可见，所以从C到B的路径不会被认为是潜在的更短路径，BFS会告诉你从A到B的最短路径权重为 3.

At the next stage, propagating from C, B is already marked as seen, so the path from C to B will not be considered as a potential shorter path, and the BFS will tell you that the shortest path from A to B has a weight of 3.

您可以使用 Dijkstra 算法 而不是 BFS 来找到加权的最短路径图形.在功能上，该算法与 BFS 非常相似，并且可以用类似于 BFS 的方式编写.唯一改变的是您考虑节点的顺序.

You can use Dijkstra's algorithm instead of BFS to find the shortest path on a weighted graph. Functionally, the algorithm is very similar to BFS, and can be written in a similar way to BFS. The only thing that changes is the order in which you consider the nodes.

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

For example, in the above graph, starting at A, a BFS will process A --> B, then A --> C, and stop there because all nodes have been seen.

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

On the other hand, Dijkstra's algorithm will operate as follows:

1. 考虑 A --> C(因为这是 A 的最低边权重)
2. 考虑 C --> B(因为这是迄今为止我们到达的任何节点的最低权重边，我们尚未考虑)
3. 考虑并忽略 A --> B，因为 B 已经被看到了.

请注意，区别仅在于检查边缘的顺序.在移动到其他节点之前，BFS 将考虑来自单个节点的所有边，而 Dijkstra 算法将始终考虑集合中权重最低的未见边连接到迄今为止看到的所有节点的边.听起来很混乱，但伪代码很简单:

Note that the difference lies simply in the order in which edges are inspected. A BFS will consider all edges from a single node before moving on to other nodes, while Dijkstra's algorithm will always consider the lowest-weight unseen edge, from the set of edges connected to all nodes that have been seen so far. It sounds confusing, but the pseudocode is very simple:

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 提供了对所发生情况的良好可视化:

This GIF from Wikipedia provides a good visualisation of what happens:

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

Notice that this looks very similar to BFS code, the only real difference is the use of a heap, sorted by distance to the node, instead of a regular queue data structure.

这篇关于对加权图使用 BFS的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！