在C++中使用BFS的最短路徑

Question

我必須編寫一個算法來查找未加權圖形中的最短路徑。我發現在未加權圖表中找到最短路徑的最佳方法是簡單地執行BFS並在達到目的地後停止。問題是我不知道如何跟蹤導致目的地的路徑。

到目前爲止，我已經想過爲每個發現的新節點創建一個新的路徑列表，但我無法弄清楚如何實現它。

此代碼似乎只要訪問每一個節點出現是工作（這是一個有點亂，不好意思）：

void shortestPath(string start, string finish, list< list<string> > adjList){ 

    queue< list< list<vertex*> >::iterator > myQueue; 
    list< list<vertex*> > listVertices = initializeVertices(start, adjList); 
    list< list<vertex*> >::iterator aux = extractList(start, listVertices); 

    myQueue.push(aux); 

    while(myQueue.size() > 0){ 

     list< list<vertex*> >::iterator vert = myQueue.front(); 

     for(list<vertex*>::iterator it = vert->begin(); it != vert->end(); it++){ 
      if((*it)->color == "white"){ 
       (*it)->color = "gray"; 
       myQueue.push(extractList((*it)->name, listVertices)); 
      } 

     } 

     list<vertex*>::iterator vertAux = vert->begin(); 
     (*vertAux)->color = "black"; 
     myQueue.pop(); 
    } 
} 

任何想法？

Answer 1

添加vertex *parent到你的頂點類不管它是什麼，還有一個輸入*vertex添加到您的push功能和改變這一行：

myQueue.push（extractList（（*吧） - >名稱，listVertices ））;

這樣：

myQueue.push（extractList（（*它） - >名，listVertices），* VERT）;

你myQueue.pop();檢查後poped節點是你的目的地，如果它是從while循環斷裂，從您的目的地，並用循環打印開始（或者不管你做什麼）每node->parent然後node = node->parent直到你到達源。

Answer 2

通過爲每個頂點v保留最短路徑樹中v的父節點的名稱，可以存儲最短路徑樹。然後，您可以通過遵循這些父指針來重建想要的最短路徑，直到到達源頂點。

Answer 3

//Breadth first Search Shortest Path 
//It is implemented using Queue Linked list representation 
//It is used to pind the shortest path from destination to the source 

#include<iostream> 
#include<stdio.h> 
#include<stdlib.h> 

using namespace std; 

typedef struct queue1{ 
    int info; 
    struct queue1 *next; 
}node; 

void createqueue(node **front1,node **rear1){ 
    *front1=*rear1=NULL; 
} 

void pushqueue(node **front1, node **rear1,int item){ 
    node *ptr; 
    ptr=(node *)malloc(sizeof(node)); 
    ptr->info=item; 
    ptr->next=NULL; 

    if((*front1)==NULL) 
     *front1=*rear1=ptr; 
    else{ 
     (*rear1)->next=ptr; 
     *rear1=ptr; 
    } 
} 

int popqueue(node **front1){ 

int item; 
    node *ptr; 
    ptr=*front1; 
    item=ptr->info; 
    *front1=ptr->next; 

return item; 
} 

int peekqueue(node *front1){ 
    return front1->info; 
} 

bool isEmpty(node *front1){ 
    if(front1==NULL) 
     return true; 
return false; 
} 

int main(){ 

    int graph[7][7]={ 
       {0,1,1,0,0,0,0}, 
       {1,0,0,1,1,0,0}, 
       {1,0,0,0,0,1,1}, 
       {0,1,0,0,0,0,0}, 
       {0,1,0,0,0,0,0}, 
       {0,0,1,0,0,0,0}, 
       {0,0,1,0,0,0,0}, 
      }; 

    int src; 
    cout << "Following is Breadth First Traversal (starting from vertex 0) \n"; 
    cin>>src; 

    int parent[10]; 
    parent[src]=-1; //Source is the root node 

    cout<<"Breadth First Search\n"; 

node *front1; 
node *rear1; 
int choice,element,temp; 

createqueue(&front1,&rear1); 
pushqueue(&front1,&rear1,src); 

bool visited[7]; 

for(int i=0;i<7;i++) //Mark all nodes as visited as false 
    visited[i]=false; 


    while(!isEmpty(front1)){ 
     src=popqueue(&front1); 
     cout<<src<<"\t"; 
     if(!visited[src]){ 
      for(int i=0;i<7;i++){ 
       if(graph[src][i] && !visited[i]){ 
        parent[i]=src;  //TO get the predessecor of the node which will help in backtracking 
        pushqueue(&front1,&rear1,i); 
       } 
      } 
     visited[src]=true; 
     } 
    } 

int destination; 
cout<<"\nEnter destination = \n"; 
cin>>destination; 

int j=destination; 
cout<<"Path from "<<j<<" to root node is as follows\n"; 

//Backtrack from destination to root node 
do{ 
    cout<<""<<j<<"\t"; 
    j=parent[j]; 
}while(j!=-1); 

cout<<"Thank You\n"; 

return 0; 
}