1

キューに問題があります。グラフをモデリングして、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;
}
4

1 に答える 1

3

あなたの問題は微妙ですが、に関連していq.push(&nb[i])ます。あなたがしているのは、ベクトル内の場所にポインターを追加することです。これは、MyVertexオブジェクトにポインターを追加することと概念的に同じではありません。近隣のベクトルには、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 の DATA ではなく、 vector の LOCATION を参照しています。

メソッドをそのまま維持したい場合、これはgetNeighborsのベクトルを返すように変更する必要があることを意味しますMyVertex*。

ポインターではなく、単にBreadthFirstSearch2 つを取るように編集する必要があります。MyVertex&その後q、 a queue<MyVertex>、vtoMyVertexに変更し、最後q.push(&nb[i])に just に変更する必要がありますq.push(nb[i])。

于 2011-05-27T17:50:41.760 に答える