Algoritmos y Estructuras de Datos (VJ1215)

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

vector<int> GrafoNoDirigido::arbolDeCaminosOptimosConPesos(int origen) const { // Algoritmo de Dijkstra
                                                                               // Suponemos arcos de peso no negativo

   int cantidadDeVertices = vertices.size();
					       
   ColaDePrioridadDecrementable colaDePrioridad(cantidadDeVertices - 1);

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

   pesoCaminoOptimo[origen] = 0;
   padre[origen] = -2;

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

   while (! colaDePrioridad.estaVacia()) {
      int verticeElegido = colaDePrioridad.eliminarMinimo();
      estaEnLaColaDePrioridad[verticeElegido] = false;
      for (Arco * arco = vertices[verticeElegido].primerArco; arco != nullptr; arco = arco->siguiente) {
	 int vecino = arco->vecino;
	 if (estaEnLaColaDePrioridad[vecino]) {
	    float nuevoPeso = pesoCaminoOptimo[verticeElegido] + arco->peso;
	    if (nuevoPeso < pesoCaminoOptimo[vecino]) {
	       pesoCaminoOptimo[vecino] = nuevoPeso;
	       padre[vecino] = verticeElegido;
	       colaDePrioridad.cambiarPrioridad(vecino, nuevoPeso);
	    }
	 }
      }
   }

   return padre;

}
      

El algoritmo de Dijkstra también se puede implementar como sigue, sin utilizar el vector de booleanos anterior, porque si vecino ya ha salido de la cola de prioridad, el valor de nuevoPeso no será menor que el de pesoCaminoOptimo[vecino].

vector<int> GrafoNoDirigido::arbolDeCaminosOptimosConPesos(int origen) const { // Algoritmo de Dijkstra
                                                                               // Suponemos arcos de peso no negativo

   int cantidadDeVertices = vertices.size();
					       
   ColaDePrioridadDecrementable colaDePrioridad(cantidadDeVertices - 1);

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

   pesoCaminoOptimo[origen] = 0;
   padre[origen] = -2;

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

   while (! colaDePrioridad.estaVacia()) {
      int verticeElegido = colaDePrioridad.eliminarMinimo();

      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);
	 }
      }
   }

   return padre;

}
      

También se podría finalizar si el verticeElegido que sale de la cola de prioridad cumple que pesoCaminoOptimo[verticeElegido] vale infinito: eso indicaría que tanto él, como todos los vértices que puedan quedar todavía en la cola de prioridad, son inalcanzables desde el vértice origen.

vector<int> GrafoNoDirigido::arbolDeCaminosOptimosConPesos(int origen) const { // Algoritmo de Dijkstra
                                                                               // Suponemos arcos de peso no negativo

   int cantidadDeVertices = vertices.size();
					       
   ColaDePrioridadDecrementable colaDePrioridad(cantidadDeVertices - 1);

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

   pesoCaminoOptimo[origen] = 0;
   padre[origen] = -2;

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

   while (! colaDePrioridad.estaVacia()) {
      int verticeElegido = colaDePrioridad.eliminarMinimo();

      if (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);
	 }
      }
   }

   return padre;

}