Ricostruzione cammini minimi Floyd-Warshall

Messaggioda dorindo » 18/02/2018, 14:43

Salve , la mia domanda è la seguente .
Non mi riferisco all'ambito della programmazione o pseudo-programmazione , ma alla constatazione finale che porta al risultato .
Mi spiego : ho due matrici
D : matrice di adiacenza (con il peso degli archi nelle rispettive posizioni)
P: matrice dei predecessori

Ad ogni iterazione k (con K=0,1,..,n con n numero dei nodi) considero il cammino minimo da un nodo i ad un nodo j vincolato alla condizione che ad ogni iterazione k si può passare esclusivamente per nodi con indice >= k ) .

Una volta terminata l'operazione (quando K=n) ho sempre le due matrici D e P (opportunamente adeguate dopo i vari step dell'algoritmo) .
In particolare dalla matrice P del predecessori 'finali' dovrei essere in grado di ricostruire il cammino minimo , ma non riesco a capire come valutare la matrice P finale .

Potreste aiutarmi ?

PS : l'algoritmo di Floyd-Warshall non è altro che l' algoritmo di Dijkstra con la condizione aggiuntiva di poter prendere in pasto pesi degli archi negativi
dorindo
Starting Member
Starting Member
 
Messaggio: 5 di 12
Iscritto il: 10/01/2018, 14:19

Re: Ricostruzione cammini minimi Floyd-Warshall

Messaggioda dorindo » 20/02/2018, 20:29

Mi rispondo da solo :
- i pesi dei cammini minimi per ogni coppia si ricavano dall'ultima matrice D trovata ( con indice k=n o k-1 nel caso matrice per (k-1) = matrice per k).
Ad esempio in riga1 ,colonna2 avremo il peso del cammino minimo tra nodo1 e nodo2 .
- il cammino di peso minimo si ricava dall'ultima matrice P dei predecessori trovata (vale lo stesso discorso sull'indice fatto per la matrice D) ; nel particolare l'ultima riga (relativa al nodo di indice più grande) permette di ricostruire questo cammino 'a ritroso' .
dorindo
Starting Member
Starting Member
 
Messaggio: 6 di 12
Iscritto il: 10/01/2018, 14:19


Torna a Analisi Numerica e Ricerca Operativa

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite