.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- [HELP] Algoritmo ultimo appello (http://www.dsy.it/forum/showthread.php?threadid=29256)

Algoritmo ultimo appello

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)