Algoritmos y Estructuras de Datos (VJ1215)

Se muestra a continuación cómo utilizar el algoritmo de Dijkstra para resolver el problema planteado.

vector<bool> GrafoDirigido::destinosValidos(int origen, float energia) const {

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

   vector<float> energiaCaminoOptimo(cantidadDeVertices, numeric_limits<float>::infinity());
   vector<bool> esDestinoValido(cantidadDeVertices, false);

   energiaCaminoOptimo[origen] = 0;

   for (int v = 0; v < cantidadDeVertices; v++)
      colaDePrioridad.insertar(v, energiaCaminoOptimo[v]);

   while (! colaDePrioridad.estaVacia()) {
      int verticeElegido = colaDePrioridad.eliminarMinimo();
      if (energiaCaminoOptimo[verticeElegido] <= energia)
	 esDestinoValido[verticeElegido] = true;
      else
	 return esDestinoValido;
      for (Arco * arco = vertices[verticeElegido].primerArcoDeSalida; arco != nullptr; arco = arco->siguiente) {
	 int vecino = arco->vecino;
	 float energiaAlternativa = energiaCaminoOptimo[verticeElegido] + arco->peso;
	 if (energiaAlternativa < energiaCaminoOptimo[vecino]) {
	    energiaCaminoOptimo[vecino] = energiaAlternativa;
	    colaDePrioridad.cambiarPrioridad(vecino, energiaAlternativa);
	 }
      }
   }

   return esDestinoValido;

}
      

La siguiente solución también sería válida, pero es preferible la anterior porque termina cuando no hace falta seguir.

vector<bool> GrafoDirigido::destinosValidos(int origen, float energia) const {

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

   vector<float> energiaCaminoOptimo(cantidadDeVertices, numeric_limits<float>::infinity());
   vector<bool> esDestinoValido(cantidadDeVertices, false);

   energiaCaminoOptimo[origen] = 0;
   esDestinoValido[origen] = true;
	       
   for (int v = 0; v < cantidadDeVertices; v++)
      colaDePrioridad.insertar(v, energiaCaminoOptimo[v]);

   while (! colaDePrioridad.estaVacia()) {
      int verticeElegido = colaDePrioridad.eliminarMinimo();
      for (Arco * arco = vertices[verticeElegido].primerArcoDeSalida; arco != nullptr; arco = arco->siguiente) {
	 int vecino = arco->vecino;
	 float energiaAlternativa = energiaCaminoOptimo[verticeElegido] + arco->peso;
	 if (energiaAlternativa < energiaCaminoOptimo[vecino]) {
	    energiaCaminoOptimo[vecino] = energiaAlternativa;
	    colaDePrioridad.cambiarPrioridad(vecino, energiaAlternativa);
	    if (energiaAlternativa <= energia)
	       esDestinoValido[vecino] = true;
	 }
      }
   }

   return esDestinoValido;

}