I'm trying to make an adaptation of djikstra's shortest path to A* algortithm but I'm having some difficulties:
This is my dijkstra's algorithm:
template<class T>
void Graph<T>::DijkstraShortestPath(const T &start){
for(unsigned i=0; i<getNumVertex(); i++){
vertexSet[i]->path = NULL;
vertexSet[i]->setDistance(INF);
vertexSet[i]->processing = false;
}
Vertex<T> *s = vertexSet[addVertex(start)];
s->setDistance(0);
vector<Vertex<T>*> pq;
pq.push_back(s);
make_heap(pq.begin(), pq.end());
while(!pq.empty()){
s = pq.front(); // diferente do git daquele gaj
pop_heap(pq.begin(), pq.end());
pq.pop_back();
for(unsigned i=0; i<s->adj.size(); i++){
Vertex<T> *w = s->adj[i].dest;
if( (s->distance + s->adj[i].length) < w->distance){
w->setDistance(s->distance + s->adj[i].length);
w->path = s;
if(!w->processing){
w->processing = true;
pq.push_back(w);
}
make_heap(pq.begin(), pq.end(), vertex_greater_than<T>());
}
}
}
}
which is working perfectly fine. But now I'm struggling trying to adapt this algorithm to aStar and the deadline is almost over. In my head I got what I need to do but I messing up when trying to code it.
I could use any help.
Thanks in advance
Regards
Aucun commentaire:
Enregistrer un commentaire