使用 BFS，有没有办法找到从所有顶点到目标顶点的距离？

Question

假设我有一个简单的图 A -> B -> C -> D。边权重都是 1。A 是起始顶点，D 是目标顶点。使用 BFS，我可以很容易地确定从 A 到 D 的距离是 3。

鉴于此，我还想找到一种有效的方法来存储从 B 到 D 和从 C 到 D 的距离，同时 BFS 算法遍历图（从 A 开始到 D 结束）。我更喜欢将 BFS 与诸如记忆/动态编程之类的东西结合起来。

PS：我的 BFS 实现确定每个顶点 v 在 v 从队列中弹出后的邻居。因此，不可能在图中向后移动，即从 D 到 A。

Answer 1

A到D的距离与所有圆弧方向反转后D到A的距离相同。只需构建一个转置图，然后运行来自 D 的 BFS，直到到达每个节点并记录距离。一些伪代码看起来像这样：

distances = {}
visited = {source_node}

frontier = queue([(target_node, 0)])
while !frontier.empty():
    node, distance = frontier.pop()
    distances[node] = distance
    for nei in node.neighbors:
        if nei not in visited:
            frontier.push((nei, distance + 1))
            visited.insert(nei)

最后您将得到一张地图 distances，其中 distances[node] 是从 node 到目标顶点的距离。

请注意，在 BFS 中，您永远不需要倒退。向后走永远不会找到最短路径，因为您要增加额外的距离才能到达每个目标。

使用 BFS，有没有办法找到从所有顶点到目标顶点的距离？

Using BFS, is there a way to find the distance from all the vertices to the goal vertex?

algorithm

graph

dynamic-programming

graph-algorithm

shortest-path