使用BFS算法獲取兩個節點之間的最短路徑

Question

我試圖通過節點圖做廣度優先搜索遍歷，之後我將嘗試找到節點與另一個節點之間的最短距離。這是維基百科的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 

我有我自己的節點類設置爲最大節點的距離。我的版本基於第一個代碼的風格：

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代碼來執行此操作？如果在這個循環內部是不可能的，那麼還有什麼其他的方式來做到這一點？

請告訴我，如果我的代碼有任何混淆或我在問什麼。謝謝！

Answer 1

通常BFS算法僅僅是爲了首先以呼吸的方式來遍歷圖中的所有節點。正如通常使用遞歸實現的DFS（深度優先）算法一樣。

爲了找到你需要修改算法的最短距離的目的：

if neighbor->distance == max 

需要是：

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

雖然這將導致完全相同的算法。但是如果圖的邊緣的距離不是1，那麼這是必需的。

使用你的算法試圖找到nodeA上最短距離到NodeB

1. 運行BFS（G，nodeA上）
2. 答案是nodeB->距離
3. 您還可以找到最短路徑通過node-> prev然後遍歷圖，直到到達nodeA

如果所有邊的距離爲1，則可以在第一次找到nodeB時停止算法。然而，如果你的邊緣有可變的距離，你將需要運行BFS算法來完成。

找到圖表2個節點之間的最短路徑，最好的辦法通常是通過使用Dijkstra's Algorithm

它有一些相似之處呼吸優先搜索，但速度更快，因爲優先級隊列的使用來完成的。