1

私のダイクストラアルゴリズムは、パスを見つけるためにうまく機能します。今、私は自分が行った道を示すために戻ってきたいと思っています. 訪問した頂点をマークし、「前」から来た頂点へのポインターを与えます。残念ながら、これらのポインターは while ループでループするときに何らかの方法で操作されるため、最後の頂点はどこから来たのかわかりません。手伝って頂けますか？

おそらく、それは私が得られないポインタの問題です。コピー コンストラクターと =operator があります。 

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; 
}
4

1 に答える 1

0

あなたはたくさんのコードを省いていますが、あなたはDistanceノードのを調整しているようです-そしてそれを設定しているようですprev-最初にそれがすでにより少ないものを持っているかどうかをチェックしませんDistance。また、パスを見つけたら、設定を停止しますprev。これにより、後で短いパスを見つけた場合に、そのノードがマークされない可能性があります。

于 2011-06-01T14:35:36.340 に答える