我必须编写一个算法来找到未加权图中的最短路径。我发现在未加权图中找到最短路径的最佳方法是简单地执行 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();
}
}
有什么想法吗?
最佳答案
您可以通过为每个顶点 v
保存最短路径树中 v
的父节点的名称来存储最短路径树。然后,您可以按照这些父指针重建所需的最短路径,直到到达源顶点。
关于c++ - 在 C++ 中使用 BFS 的最短路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26408833/