[C] BFS e cammino minimo

[gepeppe]

Salve a tutti, ho implementato l'algoritmo BFS su una lista di adiacenze, ma non riesco proprio a capire come ricavare il cammino minimo da un nodo A a un nodo finale B...mi date una mano??? Ecco il mio algoritmo:

la coda la realizzo con due puntatori ed estraggo sempre da primo, poi adiacente mi restituisce la lista di adiacenza del nodo u estratto.

M alla fine pred[i] non contiene il cammino minimo. Come si deve modificare l'algoritmo? non riesco proprio a capirlo!!!

grazie
void BFS(Nodo *Head, int n_Tag)
{
Nodo *primo, *ultimo, *u, *v, *x, *C;
int i;

int Colore[n_Tag];
int Dist[n_Tag];
Nodo *Pred[n_Tag];

int Value;
Nodo *Temp, *Temp2;

Temp = Head;
primo = ultimo = NULL;


/*Inizializzazione*/
for(i =0; i< n_Tag; i++)
{
Colore[i] = 0;
Dist[i] = -1;
Pred[i] = NULL;
}

/*Vertice Iniziale*/
Colore[Temp -> Valore] = 1;
Dist[Temp -> Valore] = 0;
Pred[Temp -> Valore] = NULL;

accoda(&primo, &ultimo, Temp);

while(primo != NULL)
{
u = estrai(&primo, &ultimo);
printf("Estraggo: %s\n", u -> tag);
/*per ogni vertice adiacente ad u (eccetto u)*/
/*x = u -> next; */
v = Adiac(Temp, u);
if(v != NULL)
{
v = v -> next;
printf("Il cui adiacente e' %s\n", v -> tag);
}

while(v != NULL)
{
if(Colore[v -> Valore] == 0)
{
Colore[v -> Valore] = 1;
Dist[v -> Valore] = Dist[u -> Valore] + 1;
Pred[v -> Valore] = u;
accoda(&primo, &ultimo, v);
}
v = v -> next;
}
Colore[u -> Valore] = 2;
}

for(i = 1; i<n_Tag; i++)
{
if(Pred[i] != NULL) printf("%s --> ", Pred[i] -> tag);
}
}