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

问题描述

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

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

PS：我经历了这个问题。

解决方案

考虑一个像这样的图表：

  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。 B，然后A - > C，并在那里停下来，因为所有的节点都已被看到。另一方面，Dijkstra的算法将如下操作：

1. 考虑A - > C（因为这是来自A的最低边权重）
   
2. 考虑C - - > B（因为这是迄今为止我们已经到达的任何节点的最低权重边缘，我们还没有考虑）


3. 考虑并忽略A→B，因为B有已经被看到。

请注意，区别仅在于检查边缘的顺序。 BFS将在考虑到其他节点之前考虑来自单个节点的所有边，而Dijkstra的算法将始终考虑来自该集的最低权重未见的边。连接到到目前为止 所有节点的边缘。这听起来令人困惑，但伪代码很简单：

 创建堆或优先级队列
将起始节点放入堆
 dist [2 ... n] = {∞} 
 dist [1] = 0 
堆中包含项目：
顶点v =堆顶部
弹出堆顶部
连接到v的每个顶点u：
如果dist [u]> dist [v] + v的权重 - > u：
 dist [u] = dist [v] + edge v的权重 - > u 
将您的权限设置为dist dist [ 
  

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

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

。

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: I went through this question and this question.

解决方案

Consider a graph like this:

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

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.

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.

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.

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.

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

1. Consider A --> C (since this is the lowest-edge weight from A)
2. Consider C --> B (since this is the lowest-weight edge from any node we have reached so far, that we have not yet considered)
3. Consider and ignore A --> B since B has already been seen.

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]

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

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屋！