c++ - 建模最短路径算法时的队列问题

Question

我有队列问题。建模图形，我正在用 C++ 做最短路径算法。

在我的 while (!q.empty()) 中，当我返回此语句时，前面的 vertex* 会发生变化。

你能找出原因吗？

int MyMatrix::searchBreadth(MyVertex* from,MyVertex* to)
{
queue<MyVertex*> q;  
path=INFINITY;

from->visit();  
from->setDistance(0);  
q.push(from);  

//here q.front()'s attributes get changed when returning from the for-loop  
while(!q.empty())
{  
    MyVertex* v=q.front();  
    q.pop();  
    int k=v->getDistance();  
    vector<MyVertex> nb=getNeighbours(*v);  
    for(int i=0;i<nb.size();i++)  
    {  
        if(nb[i].getDistance()==INFINITY)
        {  
            nb[i].setDistance(k+1);  
            q.push(&nb[i]);  
        }

        if((nb[i].getName().compare(to->getName())==0)
           && !nb[i].isVisited())
        {
            //path found  
            int j=nb[i].getDistance();  
            if(j<path) path=j;  
        }  

        nb[i].visit();  
     }  
}  
return path;  

}   

getNeighbours() 来了

vector<MyVertex> MyMatrix::getNeighbours(MyVertex &v)
{  
    int index=0;  
    for(int l=0; l<stations.size(); l++ )
    {  
        if(stations[l].getName().compare(v.getName())==0)index=l;  
    }

    vector<MyVertex> out;  
    for(int k=0;k<matrixSize;k++)
    {  
        if(matrix[index][k].getName().compare("null")!=0)
        {  
            out.push_back(matrix[index][k].getTo());  
        }  
    }  

    return out;
}

Answer 1

你的问题很微妙，但与q.push(&nb[i])有关.您正在做的是添加指向 vector 中某个位置的指针，这在概念上与添加指向 MyVertex 的指针不同。目的。邻居 vector 包含 MyVertex “按值”对象(如果这有助于您理解问题)。

看看nb在内存中可能会有所帮助:

        0         1                   I
nb [MyVertex0|MyVertex1|   ...   |MyVertexI]
             +---------+
                  | (Notice it is NOT pointing to MyVertex1!)
&nb[1]------------+

当您推送 &nb[1] 时您正在推送地址 nb + (1 * sizeof(MyVertex)) . nb在堆栈上声明，因此该地址将位于堆栈上的某个位置。

所以当你的 for -循环回来了，nb得到刷新(可以这么说)并添加新数据。然而，你的队列q包含地址到 nb不再有效!

简单地说:您的队列引用 vector 中的位置，而不是 vector 中的数据。

如果你想保持你的方法不变，这意味着 getNeighbors需要更改以返回 MyVertex* 的 vector .

---

你应该简单地编辑 BreadthFirstSearch带两个 MyVertex& ，而不是指针。然后您将更改 q成为 queue<MyVertex> , v至 MyVertex , 最后你应该改变 q.push(&nb[i])只是 q.push(nb[i]) .