percorso minimo tra due nodi di un grafo

[gatsu85]

allora,ho un problema..io riesco a implementare l'algoritmo di floyd e warshall che mi calcola le distanze tra ciascuna coppia di nodi in un grafo..ma è possibile salvare in qualche modo i nodi del percorso minimo tra ciascuna coppia di nodi?

[Pastore12]

Originariamente inviato da gatsu85
allora,ho un problema..io riesco a implementare l'algoritmo di floyd e warshall che mi calcola le distanze tra ciascuna coppia di nodi in un grafo..ma è possibile salvare in qualche modo i nodi del percorso minimo tra ciascuna coppia di nodi?

ovviamente si
il problema è in che modo vuoi salvarli

[gatsu85]

a me serve salvare i nodi e gli archi intermedi tra due nodi dati perche dopo aver creato un grafo che contiene gli archi pesati con le distanze date dall'algoritmo di floyd e warshall devo sostituire qugli archi con i corrispondenti cammini minimi...so che è un po' ingarbugliato come discorso ma è cosi.. :-)

[Pastore12]

Se devi salvare nodi e archi da un nodo a un altro, il problema non è certo più difficile di salvare un grafo, cosa che suppongo tu abbia fatto in qualche modo..

Ma per salvataggio intendi salvare la struttura dati in memoria, o salvarla su file?

[gatsu85]

io ho solo bisogno di un algoritmo che dati in input due nodi di un grafo mi restuisca in qualche modo i nodi e gli archi attraversati...

[Pastore12]

L'idea alla base di questo algoritmo è un processo iterativo che, scorrendo tutti i nodi, ad ogni passo h si ha in una matrice A nella posizione [i,j] la distanza - pesata - minima dal nodo di indice i a quello j attraversando solo nodi di indice minore o uguale a h, se non vi è collegamento allora nella cella c'è infinito. Ovviamente alla fine (con h = numero di nodi) leggendo la matrice si ricava la distanza minima fra i vari nodi del grafo.

Quindi per h=0, d(i,j,0) = peso dell'arco (i,j) se l'arco esiste, infinito se l'arco non esiste;
per h=1, d(i,j,1) = minino tra d(i,j,0) e d(i,1,0)+d(1,j,0);
... e avanti.

Ogni volta che calcoli il minimo e lo metti nella matrice, sai anche quali nodi stai usando per fare il cammino. Quindi puoi anche salvarti in una seconda matrice s[.,.] (che può anche essere una matrice di stringhe, di grafi, di vettori...) i nodi che attraversi per andare da un nodo a un altro:

s[i,j] = insieme dei nodi per andare da i a j
(d[i,j] = costo del cammino da i a j attraverso il percorso individuato da s[i,j])

[gatsu85]

scusa ma non è molto chiaro il discorso che fai!
quello che hai illustrato è il concetto alla base dell'algoritmo di floyd e warshall, e fin qui ci siamo..il problema è proprio come salvare i nodi e archi attraversati...

[Pastore12]

Originariamente inviato da Pastore12
Ogni volta che calcoli il minimo e lo metti nella matrice, sai anche quali nodi stai usando per fare il cammino. Quindi puoi anche salvarti in una seconda matrice s[.,.] (che può anche essere una matrice di stringhe, di grafi, di vettori...) i nodi che attraversi per andare da un nodo a un altro:

Scusa, ma più chiaro di così non mi riesce.

[gatsu85]

for(int k=0; k<G.lunghezza; k++){

for(int i=0; i<G.lunghezza; i++){
for(int j=0; j<G.lunghezza; j++){
if(distanze[i][k]+distanze[k][j]<distanze[i][j]) distanze[i][j] = distanze[i][k]+distanze[k][j];

}



Questo è il codice che mi calcola la matrice delle distanze...Quali sono secondo te i nodi attraversati,che quindi devo salvare?

[Pastore12]

if(distanze[i][k]+distanze[k][j]<distanze[i][j])

allora i nodi attraversati dal nodo i al nodo j, al passaggio k, sono i nodi attraversati dal nodo i al nodo k più i nodi dal nodo k al nodo j, calcolati al passaggio k-1

else

i nodi attraversati dal nodo i al nodo j, al passaggio k, sono i nodi attraversati dal nodo i al nodo j, al passaggio k-1

Siccome per k=0 i nodi attraversati li conosci concretamente, allora li puoi calcolare anche per tutti i valori di k successivi.