使用BFS算法处理带权图

Question

使用BFS算法处理带权图

algorithmgraphshortest-pathbreadth-first-search

50

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

我想知道为什么它不能用于加权图的确切原因/解释。是由于边的权重还是其他原因？有人能够解释一下吗? 我感到有些困惑。

PS：我查阅了这个问题和这个问题。

- user2125722

4

即使在无权图中，你也不能使用深度优先搜索来寻找最短路径；而广度优先搜索可以做到这一点。 - aspen100

3个回答

9

尽管如此，但是在带权图中你可以使用BFS/DFS算法，只需稍微改变一下图的结构。如果你的图中边的权重为正整数，那么你可以用权重为1的n条边替换一条权重为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，那么可以考虑使用该算法，但通常情况下该算法的性能可能不是很好。

- Lrrr

1

谢谢，这是可以做到的，但在权重相当大的情况下可能不可行，对吧？ - user2125722

@PartiallyFinite 我明白了。谢谢 :D - user2125722

@Lrrr在您的答案中提到时间复杂度是O(V * M)，但它不会像PartiallyFinite所提到的那样取决于边的数量吗？ - user2125722

1

只有一个更正需要做，其余都是正确的，即使您用n个边和(n-1)个节点替换每个边的权重，也不能使用DFS来找到最短路径。 - Veerendra Singh

@VeerendraSingh 我不认为有什么问题。它似乎等同于Dijkstra算法，尽管效率较低。 - wizzwizz4

2

老师提到BFS / DFS不能直接用于在加权图中查找最短路径。首先，DFS无法用于最短路径。其次，this answer正确解释了为什么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

来源：

- ggorlen

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Greg · Accepted Answer

考虑一个类似于这样的图：

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]

这张来自Wikipedia的GIF图很好地展示了发生的事情：

Dijkstra

注意，这看起来非常类似于BFS代码，唯一的真正区别在于使用一个按节点距离排序的堆，而不是普通队列数据结构。