Backtracking: buscando el camino mínimo en un grafo

Código en C++ de un algoritmo (usando backtracking) que busca el camino óptimo (de coste mínimo) en un grafo entre un vértice y todos los demás (algoritmo de Dijkstra).

Función de búsqueda de camino óptimo (Backtracking)
CurrentPath debe estar inicializado al primer elemento del grafo, y CurrentCost debe estar inicializado a 0.

void CBacktracking::Process(CNodeList CurrentPath, int CurrentCost){
        // Funció que gestiona el display de l'arbre.
        ExpandTree(CurrentPath,CurrentCost);

        // Ultim node del cami actual
        int node=CurrentPath.GetLastNode();
        int numveins,i=0;

        // Si l'ultim node del cami actual es igual al node final, hem acabat
        if(node != FinalNode) {
                // Llista de veins del node a processar
                CNodeList veins=Graf.GetNeighbourgs(node);
                // Nombre de veins del node a processar
                numveins=veins.GetNumNodes();
                // Processem per cada vei del node
                while(i<numveins) {
                       // Si ja hem passat per aquest node, no tornem a processar
                        if(!CurrentPath.NodeExists(veins[i])) {
                                // Fem una copia del cami actual
                                CNodeList PathAux=CurrentPath;
                                // Posem cada vei del node en la llista auxiliar
                                PathAux.PushBack(veins[i]);
                                // Fem una copia del cost actual, i li sumem el cost de connexio amb el vei
                                int CostAux=CurrentCost+Graf(CurrentPath.GetLastNode(), veins[i]);
                                // Cridem a la funcio process de nou
                                Process(PathAux,CostAux);
                        }
                i++;
                }
        }
        else
        {
                // Si el Cost actual es mes petit que el millor cost trobat fins al moment
                // i no estem al moment inicial (BestCost=0), gravem el millor cami i cost
                if(CurrentCost<BestCost || BestCost==0 ) {
                        BestCost=CurrentCost;
                        BestPath=CurrentPath;
                }
        }
        RestoreTree();
        }
Clase CNodeList (CNodeList.h)

class CNodeList : private std::vector<int>
{
public:
        CNodeList();
        virtual ~CNodeList();

        int     GetFirstNode() const ;  // ::Retorna el primer element de la llista actual
        int     GetLastNode() const;    // ::Retorna l'últim element de la llista actual
        int     GetNumNodes() const;    // ::Retorna el nombre de nodes de la llista actual
        bool IsEmpty() const;                           //::Cert si la llista actual és buida
        bool NodeExists(int Num) const;    // ::Mira si un node és a la llista actual
        int& operator[](int Index) const;  // ::Operador d'accés a un node concret
        int& operator[](int Index);                // ::Operador d'accés a un node concret
        void PushBack(int Num);                    // ::Afegeix un node al final de la llista actual
        void PopBack();                                    // ::Treu l'últim node de la llista actual
        CNodeList operator+(int Elem);   // ::Permet sumar un node a una llista, per obtenir-ne una, de nova,
                                                                         // amb aquest node afegit al final.

};
Funciones clase CNodeList (CNodeList.cpp)

int     CNodeList::GetFirstNode() const
{
        return *begin();
}


int     CNodeList::GetLastNode() const
{
        return *(end()-1);
}

int     CNodeList::GetNumNodes() const
{
        return size();
}

int& CNodeList::operator[](int Index)
{
        return *(begin()+Index);
}

int& CNodeList::operator[](int Index) const
{
        return int(*(begin()+Index));
}

bool CNodeList::IsEmpty() const
{
        return empty();
}

bool CNodeList::NodeExists(int Num) const
{
        return (std::find(begin(),end(),Num)!=end());
}

void CNodeList::PushBack(int Num)
{
        push_back(Num);
}

void CNodeList::PopBack()
{
        pop_back();
}

CNodeList CNodeList::operator+(int Num)
{
        CNodeList Tmp(*this);
        Tmp.PushBack(Num);
        return Tmp;
}



 


Trackback

Trackback URL for this entry:
http://www.gra2.com/trackback.php/20040620202454244

No trackback comments for this entry.

Comments

Post a comment

eso está muy bien, pero la declaración de las estructuras? podrías ponerlas plis?

Anonymous on Monday, January 10 2005 @ 12:20 PM CET Reply | #

He puesto la clase CNodeList, creo que es lo que pedías, espero que te sirva.

Saludos,
Dani.

---
And love, is not the easy thing, the only baggage you can bring, is all
that you can't leave behind.
- Bono, The Edge, Adam Clayton and Larry Mullen

daniel on Monday, January 10 2005 @ 09:39 PM CET Reply | #

Search



About

newton.gra2.com is a blog about technology, opinion and random thoughts written by Daniel Alvarez, a computer engineer currently living in Zurich, Switzerland.

Topics

News (20/0)
Manuals (24/0)
Security (7/0)
Music (3/0)
Weeklog (1/0)
Personal (34/0)
Photos (3/0)
Opinion (14/0)
Windows (5/0)

Blogroll

Pros i contres (Jordi)
Entrepa de fusta (Oriol)
Spaghetti Code (Isaac)
Made in net (Eric)
Nogare (Juan)
Blog de Isaac Jimenez
Web d'en Jaume Benet
Montcada Wireless (Fran)
Blog d'en Ricard Forniol
Angela Fabregues
in.solit.us

Libertad Digital
FOX News
The Wall Street Journal
The Washington Times
The Jerusalem Post

Michelle Malkin
Eurabian News
Nihil Obstat
Barcepundit
Expose the left
Davids Medienkritik
Johan Norberg
Ayaan Hirsi Ali

User Functions

:

:


Lost your password?

Latest posts

Stories

No new stories

Comments last 2 days


Trackbacks last 2 days

No new trackback comments

Links last 2 weeks

No recent new links