Algoritmos y Estructuras de Datos (VJ1215)

En este ejercicio podemos aplicar de nuevo un razonamiento que hemos visto en el ejercicio 3.c del tema 6: movernos utilizando arcos de entrada.

Para resolver eficientemente el problema podemos aplicar el algoritmo de Dijkstra 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.

El algoritmo puede terminar porque se han encontrado las ambulancias necesarias o porque no hay suficientes. En la siguiente versión del algoritmo se detecta que no hay suficientes ambulancias cuando la cola de prioridad se queda vacía y también cuando desde los vértices que quedan en la cola de prioridad no se puede llegar al destino (porque tienen peso infinito).

#define INFINITO numeric_limits<float>::infinity()

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

   int cantidadDeVertices = vertices.size();

   ColaDePrioridad colaDePrioridad(cantidadDeVertices);

   vector<float> tiempoMinimo(cantidadDeVertices, INFINITO);

   tiempoMinimo[destino] = 0;

   for (int v = 0; v < cantidadDeVertices; v++)
      colaDePrioridad.insertar(v, tiempoMinimo[v]);

   while (! colaDePrioridad.estaVacia()) {
      int verticeElegido = colaDePrioridad.eliminarMinimo();
      if (tiempoMinimo[verticeElegido] == INFINITO) {
	 cout << "Si hay mas ambulancias no pueden llegar" << endl;
	 return;
      }
      if (ambulancia[verticeElegido] != -1) {
	 cout << "Elegida ambulancia " << ambulancia[verticeElegido];
	 cout << " (tiempo de llegada estimado: " << tiempoMinimo[verticeElegido] << ")" << endl;
	 if (--ambulanciasNecesarias == 0) {
	    cout << "Conseguidas las ambulancias necesarias" << endl;
	    return;
	 }
      }
      for (Arco * arco = vertices[verticeElegido].primerArcoDeEntrada; arco != nullptr; arco = arco->siguiente) {
	 int vecino = arco->vecino;
	 float nuevoTiempo = tiempoMinimo[verticeElegido] + arco->peso;
	 if (nuevoTiempo < tiempoMinimo[vecino]) {
	    tiempoMinimo[vecino] = nuevoTiempo;
	    colaDePrioridad.cambiarPrioridad(vecino, nuevoTiempo);
	 }
      }
   }

   cout << "No hay mas ambulancias" << endl;

}
      

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:

#define INFINITO numeric_limits<float>::infinity()

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

   int cantidadDeVertices = vertices.size(),
       ambulanciasDisponibles = 0;

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

   ColaDePrioridad colaDePrioridad(cantidadDeVertices);

   vector<float> tiempoMinimo(cantidadDeVertices, INFINITO);

   tiempoMinimo[destino] = 0;

   for (int v = 0; v < cantidadDeVertices; v++)
      colaDePrioridad.insertar(v, tiempoMinimo[v]);

   while (! colaDePrioridad.estaVacia()) {
      int verticeElegido = colaDePrioridad.eliminarMinimo();
      if (tiempoMinimo[verticeElegido] == INFINITO) {
	 cout << "Si hay mas ambulancias no pueden llegar" << endl;
	 return;
      }
      if (ambulancia[verticeElegido] != -1) {
	 cout << "Elegida ambulancia " << ambulancia[verticeElegido];
	 cout << " (tiempo de llegada estimado: " << tiempoMinimo[verticeElegido] << ")" << endl;
	 if (--ambulanciasNecesarias == 0) {
	    cout << "Conseguidas las ambulancias necesarias" << endl;
	    return;
	 }
	 if (--ambulanciasDisponibles == 0) {
            cout << "No hay mas ambulancias" << endl;
	    return;
	 }
      }
      for (Arco * arco = vertices[verticeElegido].primerArcoDeEntrada; arco != nullptr; arco = arco->siguiente) {
	 int vecino = arco->vecino;
	 float nuevoTiempo = tiempoMinimo[verticeElegido] + arco->peso;
	 if (nuevoTiempo < tiempoMinimo[vecino]) {
	    tiempoMinimo[vecino] = nuevoTiempo;
	    colaDePrioridad.cambiarPrioridad(vecino, nuevoTiempo);
	 }
      }
   }

   cout << "No hay mas ambulancias" << endl;

}