.dsy:it. - [HELP] Algoritmo ultimo appello

.dsy:it.
//www.dsy.it

[HELP] Algoritmo ultimo appello

Posted by NoWhereMan on 31-01-2007 17:49

ciao a tutti

mi sembra di essere improvvisamente rincoglionito, ma rileggendo il testo dell'ultimo appello non riesco proprio a capire come svilupparlo in ampiezza... io l'avevo risolto in profondità, però mi è stato dato errato anche perché ho pasticciato durante la ricopiatura in bella.

comunque, dato un grafo orientato e due nodi s,u trovare la lista dei nodi che formano un cammino di lunghezza minima da s a u, se u è raggiungibile da s o restituire il valore _|_ (lista vuota)

grazie a chi darà una mano

ciao

edit: hm :/ credo di aver capito; con la visita in ampiezza si trova immediatamente il nodo di arrivo; memorizzando i nodi precedenti in modo opportuno si costruisce un albero di copertura che, risalendo a partire da U, dà come risultato la lista dei nodi del cammino minimo tra U e S (nell'albero: e quindi viceversa)