Algoritmos y Estructuras de Datos (VJ1215)

vector<int> GrafoDirigido::arbolDeCaminosOptimosSinPesos(int origen) const {

   vector<bool> visitado(vertices.size(), false);
   vector<int> padre(vertices.size(), -1);

   queue<int> cola;

   padre[origen] = -2;
   visitado[origen] = true;
   cola.push(origen);

   while (! cola.empty()) {
      int v = cola.front();
      cola.pop();
      for (Arco * arco = vertices[v].primerArcoDeSalida; arco != nullptr; arco = arco->siguiente)
	 if (! visitado[arco->vecino]) {
	    padre[arco->vecino] = v;
	    visitado[arco->vecino] = true;
	    cola.push(arco->vecino);
	 }
   }

   return padre;

}