Algoritmos y Estructuras de Datos (VJ1215)

Si todos los arcos tienen el mismo peso, encontrar un camino de mínimo peso entre dos vértices equivale a encontrar un camino de mínima cantidad de arcos, y mediante búsqueda en anchura se puede resolver eso más eficientemente que con el algoritmo de Dijkstra, con coste temporal O(|E| + |V|).

Al igual que en el apartado 17.a, para resolver eficientemente el problema planteado podemos aplicar la búsqueda en anchura una sola vez a partir del vértice destino en el grafo invertido. Trabajar con el grafo invertido es equivalente a recorrer el grafo original siguiendo los arcos de entrada en vez de los arcos de salida.

void GrafoDirigido::mostrarAmbulancias(int destino,
				       int ambulanciasNecesarias,
				       const vector<int> & ambulancia) const {

   if (ambulancia[destino] != -1) {
      cout << "La ambulancia " << ambulancia[destino] << " ya se encuentra en el destino" << endl;
      if (--ambulanciasNecesarias == 0) {
	 cout << "No hacen falta mas ambulancias" << endl;
	 return;
      }
   }

   vector<int> distancia(vertices.size(), -1);

   queue<int> cola;

   distancia[destino] = 0;
   cola.push(destino);

   while (! cola.empty()) {
      int v = cola.front();
      cola.pop();
      for (Arco * arco = vertices[v].primerArcoDeEntrada; arco != nullptr; arco = arco->siguiente)
	 if (distancia[arco->vecino] == -1) {
	    distancia[arco->vecino] = distancia[v] + 1;
	    if (ambulancia[arco->vecino] != -1) {
	       cout << "Elegida ambulancia " << ambulancia[arco->vecino];
	       cout << " (distancia en arcos: " << distancia[arco->vecino] << ")" << endl;
	       if (--ambulanciasNecesarias == 0) {
		  cout << "Conseguidas las ambulancias necesarias" << endl;
		  return;
	       }
	    }
	    cola.push(arco->vecino);
	 }
   }

   cout << "Si hay mas ambulancias no pueden llegar" << endl;

}
      

Al igual que en el apartado 17.a, añadiendo un bucle de coste O(|V|) para contar las ambulancias disponibles, podemos conseguir también que el algoritmo termine si no quedan ambulancias disponibles por encontrar:

void GrafoDirigido::mostrarAmbulancias(int destino,
				       int ambulanciasNecesarias,
				       const vector<int> & ambulancia) const {

   int ambulanciasDisponibles = 0;

   for (int a : ambulancia)
      if (a != -1)
         ambulanciasDisponibles++;

   if (ambulancia[destino] != -1) {
      cout << "La ambulancia " << ambulancia[destino] << " ya se encuentra en el destino" << endl;
      if (--ambulanciasNecesarias == 0) {
	 cout << "No hacen falta mas ambulancias" << endl;
	 return;
      }
      if (--ambulanciasDisponibles == 0) {
         cout << "No hay mas ambulancias" << endl;
         return;
      }
   }

   vector<int> distancia(vertices.size(), -1);

   queue<int> cola;

   distancia[destino] = 0;
   cola.push(destino);

   while (! cola.empty()) {
      int v = cola.front();
      cola.pop();
      for (Arco * arco = vertices[v].primerArcoDeEntrada; arco != nullptr; arco = arco->siguiente)
	 if (distancia[arco->vecino] == -1) {
	    distancia[arco->vecino] = distancia[v] + 1;
	    if (ambulancia[arco->vecino] != -1) {
	       cout << "Elegida ambulancia " << ambulancia[arco->vecino];
	       cout << " (distancia en arcos: " << distancia[arco->vecino] << ")" << endl;
	       if (--ambulanciasNecesarias == 0) {
		  cout << "Conseguidas las ambulancias necesarias" << endl;
		  return;
	       }
               if (--ambulanciasDisponibles == 0) {
                  cout << "No hay mas ambulancias" << endl;
                  return;
               }
	    }
	    cola.push(arco->vecino);
	 }
   }

   cout << "Si hay mas ambulancias no pueden llegar" << endl;

}