Проблема очереди при моделировании алгоритма кратчайшего пути - PullRequest
Новая
       44

Проблема очереди при моделировании алгоритма кратчайшего пути

1 голос
/ 27 мая 2011

У меня проблема с очередью. Моделируя граф, я делаю алгоритм кратчайшего пути в 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;
}

1 Ответ

3 голосов
/ 27 мая 2011

Ваша проблема неуловима, но связана с 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, которые больше не действительны!

Проще говоря: ваша очередь ссылается на LOCATION в векторе, а не на DATA в векторе .

Если вы хотите оставить свой метод как есть, это означает, что getNeighbors необходимо изменить, чтобы он возвращал вектор MyVertex*.

Вы должны просто отредактировать BreadthFirstSearch, чтобы взять два MyVertex&, а не указатели.Затем вы должны изменить q на queue<MyVertex>, v на MyVertex, и, наконец, вы должны изменить q.push(&nb[i]) на q.push(nb[i]).

...