Curso 2024/2025
#include <limits> // infinity #include "ColaDePrioridad.h" vector<int> GrafoNoDirigido::arbolDeCaminosOptimosConPesos(int origen) const { // Algoritmo de Dijkstra // Suponemos arcos de peso no negativo int cantidadDeVertices = vertices.size(); ColaDePrioridad colaDePrioridad(cantidadDeVertices); 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(); ColaDePrioridad colaDePrioridad(cantidadDeVertices); 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(); ColaDePrioridad colaDePrioridad(cantidadDeVertices); 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; }