[C] stampa a video di un percorso minimo tramite Dijkstra

[Tony Hak]

ciao !

ho implementato l'algoritmo dei cammini minimi di dijkstra. Ho quindi un vettore contenente tutte le distanze aggiornate dal nodo di partenze. Come posso ora stampare il percorso minimo da un vertice ad un altro ? Ho anche un vettore con le rispettive posizioni delle citta'. esempio :

distanze 0 9 14 15 32 34 45 50

posizioni 0 1 5 6 2 4 3 7

Se voglio ad esempio arrivare all'ultimo vertice partendo dal primo come la eseguo la stampa a video ? grazie mille !

[71104]

di per se' quelle informazioni non bastano, a meno che non metti in atto un ulteriore algoritmo per trovare i nodi del cammino.
Dijkstra oltre alle distanze trova anche il cosiddetto vettore dei padri, che è quello che serve a te.

[Tony Hak]

scusa..come si ricava il vettore dei padri ? sarebbe dei precedenti ? ...

[71104]

Originariamente inviato da Tony Hak

scusa..come si ricava il vettore dei padri ? sarebbe dei precedenti ? ...

si. per il come si ricava, fa parte dell'algoritmo
mi pare che ogni volta che fai un rilassamento, e decidi quindi che la distanza dalla sorgente s a un certo nodo v viene minimizzata passando per un certo nodo u, u diventa il padre (o predecessore) di v. non sono molto sicuro che Dijkstra funzionasse esattamente così, vado a memoria.

[Tony Hak]

buongiorno ! ... tu quindi dici di mettere nel vettore posizioni solo le posizioni che vengono rilassate... ma..cosi' non vengono messe anche vertici che non fanno parte del cammino ? ..sono un po' confuso

[71104]

Originariamente inviato da Tony Hak

buongiorno ! ... tu quindi dici di mettere nel vettore posizioni solo le posizioni che vengono rilassate... ma..cosi' non vengono messe anche vertici che non fanno parte del cammino ? ..sono un po' confuso

ripeto che non lo so, vado a memoria (ho realizzato un'implementazione di Dijkstra lo scorso Ottobre, due mesi per me sono stati una buona gomma ). aiutati con Wikipedia: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

[lattone]

Devi memorizzare il vettore dei padri, o dei successori, vedi tu.

Ogni volta che l'algoritmo scopre un percorso migliore viene aggiornato il successore ( o padre). In questo modo ogni nodo conosce il successivo.

[71104]

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.

[mamodjembe]

Salve ragazzi,sapete dove posso trovare il codice in c dell algoritmo di dijkstra?sapete dove posso trovare qullo di bellman-ford e di floyd warshall???
PLEASE HELP ME!!!!!!!!

[marko.fatto]

Originariamente inviato da mamodjembe

Salve ragazzi,sapete dove posso trovare il codice in c dell algoritmo di dijkstra?sapete dove posso trovare qullo di bellman-ford e di floyd warshall???
PLEASE HELP ME!!!!!!!!

dovresti prima provare a farlo e poi chiedere qui se hai qualcosa che non ti va