Проблема обхода графа

Question

Мой алгоритм Дейкстры отлично работает, чтобы найти путь.Теперь я хочу вернуться, чтобы показать, как я пошел.Я отмечаю посещенную вершину и даю ей указатель на вершину, которую я пришел из "prev".К сожалению, эти указатели каким-то образом манипулируют при цикле в цикле while, так что вершины в конце не знают, откуда они пришли.Вы можете мне помочь?

Возможно, это проблема с указателем, которую я не понимаю.У меня есть конструктор копирования и оператор =.

int MyMatrix::searchBreadth(MyVertex &from,MyVertex &to,int mode)  
{  
queue<MyVertex> q;//queue  
vector<MyVertex> nb;//vector of neighbours  
path=INFINITY;//path is very long  
visits.push_back(from.getName());  
from.setDistance(0);  
MyVertex n("start");  
from.setPrev(n);  
q.push(from);  
while(!q.empty())  
     {  
         MyVertex v=q.front(); 

         q.pop();
         int k=v.getDistance();
         nb.clear();
         nb = getNeighbours(v);


         for(unsigned int i=0;i<nb.size();i++)
         {
             if((!nb[i].getPrev())&&path==INFINITY) nb[i].setPrev(v);

             if(!mode){//unweighted
                if(!wasVisited(nb[i].getName())){
                    nb[i].setDistance(k+1);
                    q.push(nb[i]);
                }
             }
             if(mode){//length or weight
                 if(!wasVisited(nb[i].getName())){
                     int cost=0;
                     MyEdge e = m->getEdge(v,nb[i]);
                     if(mode==1)cost=(int) e.getLength();//length
                     if(mode==2)cost=(int) e.getWeight();//weigth
                     nb[i].setDistance(k+cost);
                     q.push(nb[i]);
                 }
             }

             if((nb[i].getName().compare(to.getName())==0) && (!wasVisited(nb[i].getName()))){//path found
                int j=nb[i].getDistance();
                if(j<path)path=j;
             }
             visits.push_back(nb[i].getName());
         }//end of for
         //end of 0size if
     }//end of while
     return path;
}

MyVertex::MyVertex()
{  
name="null";  
dist=0;  
visited=false;  
prev=0;  
}              
MyVertex::MyVertex(string name)
{
this->name=name;
visited=false;
dist=numeric_limits<int>::max();
prev=0;
}

MyVertex::~MyVertex(void)
{
if (!prev) prev=0;
}

MyVertex::MyVertex(const MyVertex& V){
this->name = V.name;
this->visited=V.visited;
    this->dist=V.dist;
this->prev=V.prev;

}

MyVertex& MyVertex::operator=(const MyVertex& L){
if (this == &L){ return *this;
  }else{

    delete prev;
    dist=L.dist;
    name=L.name;
    visited=L.visited;
    prev=L.prev;

  }

  return *this; 
}

Answer 1

Вы пропускаете много кода, но, похоже, вы настраиваете Distance узла - и устанавливаете его prev - без предварительной проверки, имеет ли он уже меньшее Distance. И как только вы нашли любой путь, вы прекращаете установку prev, так что, если вы позже найдете более короткий путь, его узлы могут быть не отмечены.