[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);
    }
}