dimanche 24 avril 2016

A star template algorithm

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