Curso 2023/2024
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; }