Exploración segura usando Dijkstra

[GabrielEValenzuela]

Descripción

Dentro del universo del juego, cada nodo representa un refugio o lugar potencialmente visitable, conectado mediante caminos con diferentes niveles de peligro. El objetivo de esta tarea es utilizar el algoritmo de Dijkstra para determinar la ruta más segura desde el refugio actual del jugador hacia un destino objetivo, minimizando el riesgo acumulado en lugar de la distancia.

Criterios de aceptación:

• Se calcula la ruta desde la posición actual del jugador hacia un refugio determinado minimizando el riesgo.

• La ruta obtenida puede mostrarse como una lista de refugios con su riesgo acumulado total.

[Danteps-4]

void dijkstra(int numVertices, int origen, int destino, const std::vector<std::vector<int>>& matrizGrafo){
  std::vector<int> distancias(numVertices, INT_MAX);
  std::vector<int> parent(numVertices, -1);
  std::priority_queue<std::pair<int,int>, std::vector<std::pair<int,int>>, std::greater<std::pair<int,int>>> pq;

  distancias[origen] = 0;
  pq.push({0, origen});

  while(!pq.empty()){
    auto [distancia, u] = pq.top();
    pq.pop();

    if(distancia > distancias[u]) {
      continue;
    }

    for(int v = 0; v < numVertices; ++v){
      if(matrizGrafo[u][v] != 0){
        int peso = matrizGrafo[u][v];
        if(distancias[u] + peso < distancias[v]){
          distancias[v] = distancias[u] + peso;
          parent[v] = u;
          pq.push({distancias[v], v});
        }
      }
    }
  }

  if(distancias[destino] == INT_MAX){
    std::cout << "No existe ruta segura desde " << origen << " hacia " << destino << std::endl;
    return;
  }

  std::stack<int> ruta;
  for(int v = destino; v != -1; v = parent[v]){
    ruta.push(v);
  }

  std::cout << "Ruta mas segura desde " << origen << " hacia " << destino << " con riesgo: " << distancias[destino] << std::endl;
  while(!ruta.empty()){
    std::cout << ruta.top();
    ruta.pop();
    std::cout << " -> ";
  }
  std::cout << std::endl;
}