Algoritmos y Estructuras de Datos (VJ1215)

#include <limits>
#define INFINITO numeric_limits<float>::infinity()

#define DESCONOCIDO -INFINITO

float GrafoDirigido::calcularCaminoOptimo(int origen,
					  int destino,
					  vector<float> & resultado,
					  vector<int> & padre) const { // Suponemos grafo aciclico

   if (resultado[destino] == DESCONOCIDO)

      if (origen == destino)
	 resultado[destino] = 0;
      else {
	 resultado[destino] = INFINITO; 
         for (Arco * arco = vertices[destino].primerArcoDeEntrada;
              arco != nullptr;
              arco = arco->siguiente) {
            float pesoIncidente = calcularCaminoOptimo(origen, arco->vecino, resultado, padre)
                                  + arco->peso;
	    if (pesoIncidente < resultado[destino]) {
	       resultado[destino] = pesoIncidente;
	       padre[destino] = arco->vecino;
	    }
	 }
      }

return resultado[destino]; // Vale INFINITO si no tiene incidentes o todos son
                           // inalcanzables desde el origen

}

void GrafoDirigido::mostrarCaminoOptimo(int origen, int destino) const {

   vector<float> resultado(vertices.size(), DESCONOCIDO);
   vector<int> padre(vertices.size(), -1);

   float peso = calcularCaminoOptimo(origen, destino, resultado, padre);
  
   if (peso == INFINITO)
      throw string ("El destino ") + to_string(destino) 
	 + string(" es inalcanzable desde el origen ") + to_string(origen);

   cout << endl << "Camino optimo de " << origen << " a " << destino << ":" << endl;
   cout << "  vertices:";
   stack<int> pila;
   for (int vertice = destino; vertice != -1; vertice = padre[vertice])
      pila.push(vertice);
   while(! pila.empty() ) {
      cout << " " << pila.top();
      pila.pop();
   }
   cout << endl << "  peso: " << peso << endl;;

}