Algoritmos y Estructuras de Datos (VJ1215)

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

#define DESCONOCIDO -INFINITO

float GrafoDirigido::pesoCaminoOptimo(int origen,
				      int destino,
				      vector<float> & resultado) 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 = pesoCaminoOptimo(origen, arco->vecino, resultado) + arco->peso;
	    if (pesoIncidente < resultado[destino])
	       resultado[destino] = pesoIncidente;
	 }
      }

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

}

float GrafoDirigido::pesoCaminoOptimo(int origen, int destino) const {

   vector<float> resultado(vertices.size(), DESCONOCIDO);

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

   return peso;

}