使用BFS算法在未加權的有向圖中找到兩個節點之間的所有最短路徑

Question

我正在研究一個問題，我需要在給定的有向未加權圖中找到兩個節點之間的所有最短路徑。我使用BFS算法來完成這項工作，但不幸的是，我只能打印一條最短路徑，而不是全部，例如，如果它們是4條長度爲3的路徑，我的算法只打印第一條路徑，但我希望打印所有路徑四條最短路徑。我在下面的代碼中想知道如何更改它，以便可以打印出兩個節點之間的所有最短路徑？

class graphNode{ 
    public: 
     int id; 
     string name; 
     bool status; 
     double weight; 
}; 


map<int, map<int,graphNode>* > graph; 


int Graph::BFS(graphNode &v, graphNode &w){ 

    queue <int> q; 
    map <int, int> map1; // this is to check if the node has been visited or not. 
    std::string str= ""; 
    map<int,int> inQ; // just to check that we do not insert the same iterm twice in the queue 


    map <int, map<int, graphNode>* >::iterator pos; 
    pos = graph.find(v.id); 
    if(pos == graph.end()) { 
     cout << v.id << " does not exists in the graph " <<endl; 
     return 1; 

    } 

    int parents[graph.size()+1]; // this vector keeps track of the parents for the node 
    parents[v.id] = -1; 


    if (findDirectEdge(v.id,w.id) == 1){ 
     cout << " Shortest Path: " << v.id << " -> " << w.id << endl; 
     return 1; 
    } //if 
    else{ 
     int gn; 
     map <int, map<int, graphNode>* >::iterator pos; 

     q.push(v.id); 
     inQ.insert(make_pair(v.id, v.id)); 

     while (!q.empty()){ 
     gn = q.front(); 
     q.pop(); 
     map<int, int>::iterator it; 
     cout << " Popping: " << gn <<endl; 
     map1.insert(make_pair(gn,gn)); 


     if (gn == w.id){//backtracing to print all the nodes if gn is the same as our target node such as w.id 
      int current = w.id; 
      cout << current << " - > "; 
      while (current!=v.id){ 
       current = parents[current]; 
       cout << current << " -> "; 
      } 
     cout <<endl; 
     } 
          if ((pos = graph.find(gn)) == graph.end()) { 
      cout << " pos is empty " <<endl; 
      continue; 
     } 
     map<int, graphNode>* pn = pos->second; 

          map<int, graphNode>::iterator p = pn->begin(); 
     while(p != pn->end()) { 
      map<int, int>::iterator it; 

      it = map1.find(p->first);//map1 keeps track of the visited nodes 
      graphNode gn1= p->second; 
      if (it== map1.end()) { 
       map<int, int>::iterator it1; 
       it1 = inQ.find(p->first); //if the node already exits in the inQ, we do not insert it twice 

       if (it1== inQ.end()){ 
        parents[p->first] = gn; 
        cout << " inserting " << p->first << " into the queue " <<endl; 
        q.push(p->first); // add it to the queue 
       } //if 
      } //if 
      p++; 
      } //while 

    } //while 
} 

我很欣賞你的所有幫助很大 謝謝， 安德拉

Answer 1

1. map<int, map<int,graphNode>* > graph聲明一個每邊有一個graphNode對象的圖形。

   一個graphNode每個節點將具有類型map<int, map<int,graphNode*> >或甚至更好，map<graphNode*, set /* or vector */<graphNode*> >或者可能更好，multimap< graphNode *, graphNode * >。

   graphNode需要存儲在您使用的任何map的單獨結構中（例如，vector或deque）。

2. int parents[graph.size()+1];是非標準的。改爲使用vector<int> parents(graph.size()+1);。

3. 要回答你的問題，你想要繼續BFS，直到你到達拓撲順序大於第一個結果的第一個節點。引入一個變量int first_id_of_next_level = v.id;。 （或者更好的辦法是使用一個指針。）當你找到一個匹配時，把它的路徑追加到路徑列表中。當gn == first_id_of_next_level，要麼return的列表，如果它不是empty或設置first_id_of_next_level = p->first，目前的父母的第一個孩子，所以你知道下一個機會停止搜索。

Answer 2

要編寫所有最短路徑，您必須編寫一個遞歸類DFS算法。運行BFS以查找到每個節點的最小距離，存儲該距離，然後從源節點運行DFS，僅分支到滿足最小路徑的節點。每當你到達目標節點時，寫下你到達那裏的路徑（你一直在你的遞歸函數中跟蹤）。請注意，您不會在DFS中標記節點。

由於該算法需要回溯，所以最好的方法是通過遞歸DFS。你可以用10寫一個BFS，但你必須維護一個堆棧來跟蹤你的回溯，這意味着你基本上是用一個手工維護的堆棧寫DFS，也就是寫一個完全相同的算法，其代碼的兩倍你需要。

請注意，最短路徑的數量並不總是多項式，因此您可能會寫入指數數量的路徑。