Algoritmos y Estructuras de Datos (VJ1215)

Podemos asociar a cada vértice v un contador contadorCaminosOptimos[v], inicializado a uno en el vértice origen y a cero en el resto de vértices, y modificar el algoritmo de Dijsktra para actualizar esos contadores así:

int GrafoNoDirigido::contarCaminosOptimos(int origen, int destino) const { // Suponemos arcos de peso positivo

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

   vector<float> pesoCaminoOptimo(cantidadDeVertices, numeric_limits<float>::infinity());
   vector<int> contadorCaminosOptimos(cantidadDeVertices, 0);

   pesoCaminoOptimo[origen] = 0;
   contadorCaminosOptimos[origen] = 1;

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

   while (! colaDePrioridad.estaVacia()) {
      int verticeElegido = colaDePrioridad.eliminarMinimo();
      cout << "Elegido: " << verticeElegido << endl;
      if (verticeElegido == destino)
	 return contadorCaminosOptimos[verticeElegido];
      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;
	    contadorCaminosOptimos[vecino] = contadorCaminosOptimos[verticeElegido];
	    colaDePrioridad.cambiarPrioridad(vecino, nuevoPeso);
	 }  else if (nuevoPeso == pesoCaminoOptimo[vecino])
	    contadorCaminosOptimos[vecino] += contadorCaminosOptimos[verticeElegido];
	 cout << "   Vecino: " << vecino << "\t" << pesoCaminoOptimo[vecino] << "\t" << contadorCaminosOptimos[vecino] << endl;
      }
   }

   return 0;

}