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

我有一个队列问题。为图形建模，我正在用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;
}

最佳答案

您的问题很微妙，但与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 -loop重新出现时，nb会刷新(可以这么说)并添加新数据。但是，您的队列q包含的nb地址不再有效!

简而言之:您的队列引用的是 vector 中的LOCATION，而不是 vector 中的DATA。

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

您应该简单地编辑BreadthFirstSearch以接受两个MyVertex&，而不是指针。然后，您可以将q更改为queue<MyVertex>，将v更改为MyVertex，最后应将q.push(&nb[i])更改为q.push(nb[i])。

关于c++ - 建模最短路径算法时的排队问题，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/6155844/