Блог

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

        if((nb[i].getName().compare(to->getName())==0)
           amp;amp; !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 amp;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(amp;nb[i]) . То, что вы делаете, это добавляете указатель на местоположение в векторе, что концептуально не совпадает с добавлением указателя на MyVertex объект. Вектор соседей содержит MyVertex объекты «по значению» (если это помогает вам понять проблему).

Взгляд на nb в памяти может помочь:

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

Когда вы нажимаете, amp;nb[1] вы нажимаете адрес nb (1 * sizeof(MyVertex)) . nb объявлен в стеке, так что этот адрес будет где-то в стеке.

Итак, когда ваш for цикл возвращается, nb обновляется (так сказать) и добавляются новые данные. Однако ваша очередь q содержит адреса в nb , которые больше не действительны!

Проще говоря: ваша очередь ссылается на МЕСТОПОЛОЖЕНИЕ в векторе, а не на ДАННЫЕ в векторе.

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

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