algoritmo di Dijkstra

[aleraimondi]

Salve, sono alle prese con questo algoritmo da sviluppare in java.
Praticamente devo elaborare un grafo tramite liste di adiacenza (l'ho fatto già) e trovare i cammini minimi a sorgente singola usando questo noto algoritmo. Quello che non capisco è come venga riempita la coda da cui si etrae il vertice con minima stima di cammino minimo.
lo pseudocodice dell'algoritmo è questo:

1 function Dijkstra(G, w, s)
2 for each vertex v in V[G] // Initializations
3 d[v] := infinity
4 previous[v] := undefined
5 d[s] := 0
6 S := empty set
7 Q := V[G]
8 while Q is not an empty set // The algorithm itself
9 u := Extract_Min(Q)
10 S := S union {u}
11 for each edge (u,v) outgoing from u
12 if d[u] + w(u,v) < d[v] // Relax (u,v)
13 d[v] := d[u] + w(u,v)
14 previous[v] := u


1 S := empty sequence
2 u := t
3 while defined previous[u]
4 insert u to the beginning of S
5 u := previous[u]


spero vivamente che qulcuno riesca a darmi una mano. ringrazio tutti.

[akyra]

in coda inserisci i vertici ordinandoli da quello che ha d[v] più piccolo a quello che a d[v] più grande...
o forse non ho capito cosa non hai capito (scusa il gioco di parole...)

[aleraimondi]

grazie mille per l'intervento!!

anche io la capisco come mi hai detto, ma scusa, quando inizializzo il vettore delle distanze D non metto 0 alla sorgente ed infinito agli altri?
è proprio questo che non capisco, come iniziaqlizzare il vettore d!!
devo per caso usare qualche algoritmo di visita dei grafi tipo la visita in ampiezza o profondità?
il mio libro dice testuali parole:
"nella coda con priorità vengono messi i nodi del grafo che hanno cammino minimo teorico minore"
tradotto io capisco che si tratti proprio del vettore D, ma sto cammino minimo teorico che cos'è?
grazie mille per ogni aiuto

[akyra]

senza dubbio devi usare un algoritmo di visita in ampiezza o in profondità per inizializzare la struttura che contiene le distanze...anche su usi un algortimo di questo tipo la coplessità totale di Dijkstra (che è O(n^2) se non sbaglio...) non ne risentirà...
logicamente il tuo libro su cui è spiegato l'algoritmo tralascia questa parte di inizializzazione, in quanto non aggiunge nulla che possa servire a comprendere meglio l'algoritmo di Dijkstra...anche perchè la didattica spesso esula da quella che è l'implementazione finale dell'algoritmo (non a caso usa pseudocodice), che invece spesso risente (come in questo caso) di problemi prettamente implementativi.

[aleraimondi]

Originariamente inviato da akyra

senza dubbio devi usare un algoritmo di visita in ampiezza o in profondità per inizializzare la struttura che contiene le distanze...anche su usi un algortimo di questo tipo la coplessità totale di Dijkstra (che è O(n^2) se non sbaglio...) non ne risentirà...
logicamente il tuo libro su cui è spiegato l'algoritmo tralascia questa parte di inizializzazione, in quanto non aggiunge nulla che possa servire a comprendere meglio l'algoritmo di Dijkstra...anche perchè la didattica spesso esula da quella che è l'implementazione finale dell'algoritmo (non a caso usa pseudocodice), che invece spesso risente (come in questo caso) di problemi prettamente implementativi.

grazie mille, provo, se ne vengo a capo posto