Algoritmos y Estructuras de Datos (VJ1215)

#include <limits> // infinity
#include "ColaDePrioridad.h"

void GrafoNoDirigido::mostrarCaminoOptimoConPesos(int origen, int destino, const vector<float> & distanciaRecta) const {

   int cantidadDeVertices = vertices.size();
					       
   ColaDePrioridad colaDePrioridad(cantidadDeVertices);

   vector<float> pesoCaminoOptimo(cantidadDeVertices, numeric_limits<float>::infinity());
   vector<int> padre(cantidadDeVertices, -1);

   pesoCaminoOptimo[origen] = distanciaRecta[origen];

   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] - distanciaRecta[verticeElegido] + arco->peso + distanciaRecta[vecino];
	 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;
   }

}