图遍历问题

Question

我的 Dijkstra 算法可以很好地找到路径。现在我想回去展示我走过的路。我标记一个访问过的顶点，并给它一个指向我来自“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 - 而没有首先检查它是否已经有较小的距离。一旦找到任何路径，就停止设置prev，这样如果以后找到更短的路径，其节点可能不会被标记。