Кратчайший путь с использованием BFS в C++

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 узла вашего назначения, если она есть, не порвутся от в то время как петлю и начните с пункта назначения и с петлей печати (или все, что вы делаете) каждый 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; 
}