Curso 2024/2025
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(); ColaDePrioridad colaDePrioridad(cantidadDeVertices); 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; }