graph-algorithm - 如何修改BFS算法找到最短距离

Question

假设在一个图中，所有边的权重=1。解释如何修改 BFS 算法以找到从 A 到 B 的最短距离 SD，即调用 SD (A,B)，其中 A 是起始顶点，B 是结束顶点。考虑 SD 问题的所有可能答案。

Answer 1

假设 A 和 B 在同一个连通图上，BFS 可以为您提供 A 和 B 之间的最短距离。

通常，BFS 接收一个起始节点，然后一次发现其邻域，这意味着它会发现距离为 1 的所有节点，然后是距离 2 的所有节点，依此类推。

让我们称将 SD 从 A 返回到 B 的 BFS 的新版本：BFS_D

所以第一个修改是给它两个参数而不是一个。BFS_D 的返回类型将变为布尔值。

现在我们有两种可能性：要么有一条从 A 到 B 的路径，要么没有。

如果有一条路径，在某个时刻，我们将从节点队列中获取 B。我们可以使用第二个队列来存储每个节点的级别，因此我们可以找到 A 到 B 的距离。

如果没有路径，我们将简单地发现所有包含 A 的连通图而不找到 B。基本上，一旦我们没有更多的节点可以访问，我们只返回 false 或 Infinity。

第三种情况可能发生，即 A == B，我们必须确保我们的代码正确处理这种情况。

这是基于维基百科代码修改后的 BFS 的简单实现：

procedure BFS_D(G,A,B):
      create a queue Q // This will store the undiscovered nodes
      create a queue D // This will store the level (distance) of each node
      enqueue A onto Q
      enqueue 0 onto D
      mark A
      while Q is not empty:
          t ← Q.dequeue()
          td ← D.dequeue()
          if t is equal to B:
              return td
          for all edges e in G.incidentEdges(t) do
              // G.opposite returns adjacent vertex 
             o ← G.opposite(t,e)
             if o is not marked:
                  mark o
                  enqueue o onto Q
                  enqueue (td + 1) onto D
      return Infinity // We have discovered all the nodes without find B, there is no path