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

