Curso 2023/2024
#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; }