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