Quote:
Originariamente inviato da lattone
Devi memorizzare il vettore dei padri, o dei successori, vedi tu.
|
nell'algoritmo di Dijkstra memorizzare il vettore dei successori non ha senso: Dijkstra se ricordo bene prende di volta in volta archi (u, v) tali che u è nell'albero costruito e v invece no, e non ricordo che altra condizione, quindi ha senso dire che u diventa il predecessore di v (il predecessore per arrivare alla radice), ma non ha senso dire che v diventa il successore di u (il successore per arrivare dove?).
al contrario il vettore (anzi, la matrice) dei successori ha senso per esempio in Floyd-Warshal, dove viene preso di volta in volta un cammino da a a b contenente da qualche parte un nodo v; quando Floyd-Warshal fa un rilassamento, cioè determina che per andare da a a b bisogna passare per v, ha senso dire che v è il successore di a per arrivare a b.