我正在尝试通过节点图进行广度优先搜索遍历,此后,我将尝试查找一个节点与另一个节点之间的最短距离。维基百科的BFS算法如下所示:

  procedure BFS(G,v) is
      let Q be a queue
      Q.push(v)
      label v as discovered
      while Q is not empty
         v ← Q.pop()
         for all edges from v to w in G.adjacentEdges(v) do
             if w is not labeled as discovered
                 Q.push(w)
                label w as discovered


我有自己的Node类,其Nodes的距离设置为max。我的版本基于第一个代码的样式:

class Node { // my version
  string name;
  vector<Node*> adj;
  int dist; // initially set to int max
  int prev;
  int index;
}

procedure BFS(G, Node* v)
    let Q be a queue
    v->distance = 0
    Q.push(v)
    label v as discovered
    while Q is not empty
      Node* n = q.front();
      v = Q.pop()
      for each node w adj vector of n
         Node* neighbor = G[w]
         if neighbor->distance == max
           neighbor->distance = n->distance + 1
           neighbor->prev = n->index
           q.push(neighbor)


我试图使此代码也找到一个节点和另一个节点之间的最短路径。例如

procedure BFS(G, Node* from, Node* to)


如何修改BFS代码来做到这一点?如果在此循环内不可能,那么还有什么其他方法可以做到?

如果我的代码或我的要求有任何混淆,请告知我。谢谢!

最佳答案

通常,BFS算法只是为了以呼吸优先的方式遍历图中的所有节点。与通常使用递归实现的DFS(深度优先)算法相对应。

为了找到最短距离,您需要修改算法:

if neighbor->distance == max


需要是:

if neighbor->distance > n->distance+1


尽管这将导致完全相同的算法。但是,如果图形的边缘的距离不是1,则这是必需的。

使用您的算法尝试查找从节点A到节点B的最短距离


运行BFS(G,nodeA)
答案在nodeB-> distance
您还可以通过以下方式找到最短路径:通过node-> prev向后走,然后遍历图形直到到达nodeA


如果所有边的距离均为1,则可以在第一次找到nodeB时停止算法。但是,如果边缘的距离可变,则需要运行BFS算法才能完成。

找到图中两个节点之间最短路径的最佳方法通常是使用Dijkstra's Algorithm

它与“呼吸优先搜索”有一些相似之处,但由于使用了优先级队列,因此速度更快。

关于c++ - 使用BFS算法获得两个节点之间的最短路径,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/28802836/

10-11 23:01
查看更多