Curso 2023/2024
#include <limits> // infinity #include "ColaDePrioridad.h" void GrafoNoDirigido::mostrarCaminoOptimoConPesos(int origen, int destino) const { int cantidadDeVertices = vertices.size(); ColaDePrioridad colaDePrioridad(cantidadDeVertices); vector<float> pesoCaminoOptimo(cantidadDeVertices, numeric_limits<float>::infinity()); vector<int> padre(cantidadDeVertices, -1); pesoCaminoOptimo[origen] = 0; for (int v = 0; v < cantidadDeVertices; v++) colaDePrioridad.insertar(v, pesoCaminoOptimo[v]); while (! colaDePrioridad.estaVacia()) { int verticeElegido = colaDePrioridad.eliminarMinimo(); // cout << "vertice elegido: " << verticeElegido << "\tpeso: " << pesoCaminoOptimo[verticeElegido] << endl; if (verticeElegido == destino || pesoCaminoOptimo[verticeElegido] == numeric_limits<float>::infinity()) break; for (Arco * arco = vertices[verticeElegido].primerArco; arco != nullptr; arco = arco->siguiente) { int vecino = arco->vecino; float nuevoPeso = pesoCaminoOptimo[verticeElegido] + arco->peso; if (nuevoPeso < pesoCaminoOptimo[vecino]) { pesoCaminoOptimo[vecino] = nuevoPeso; padre[vecino] = verticeElegido; colaDePrioridad.cambiarPrioridad(vecino, nuevoPeso); } } } if (padre[destino] == -1) cout << "No existe camino desde " << origen << " hasta " << destino << endl; else { int v = destino; cout << "Camino optimo: " << v; while (v != origen) { v = padre[v]; cout << " --- " << v; }; cout << endl; } }