algoritmo di Floyd-Warshall

L'algoritmo di Floyd-Warshall calcola il cammino minimo per tutte le coppie di un grafo pesato e orientato con una complessità .L'idea alla base di questo algoritmo è un processo iterativo che, scorrendo tutti i nodi, ad ogni passo h si ha (data 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. Premesso ciò, si può dire che il problema si risolve in programmazione dinamica facendo uso teoricamente di una matrice cubica dove le ordinate e le ascisse sono i e j, mentre h è la profondità. Praticamente, invece, possiamo usare una sola matrice reiterandola piano per piano in h. Si comincia col ricavare la matrice di adiacenza del grafo (infinito dove non vi è collegamento), poi basandoci su di essa cominciamo, in ogni passo h successivo si esaminano ogni cella[i,j] della matrice A: se la somma della distanza tra i ed il nuovo nodo in esame h sommata alla distanza fra h e j è minore della distanza direttamente fra i e j allora si sostituisce quest'ultimo con la precedente somma (per andare dal nodo i al nodo j mi conviene passare per il nodo h). Detto in modo un po' più formale se (Ah-1[i,h] + Ah-1[h,j]) < Ah-1[i,j] allora Ah[i,j] = (Ah-1[i,h] + Ah-1[h,j]) dove h è il piano che stiamo analizzando. Sotto potete vedere un algoritmo in pseudocodice del procedimento descritto: Inizializzazioneint [0..n, 0..n] dist;for i := 1 to nfor j := 1 to ndist[i][j] := Weight(i,j); dove Weight(i,j) è una funzione che riporta il peso dell'arco da i a j, 0 nel caso in cui i = j oppure infinito se non esiste un arco da i da j nel grafo. floydWarshall(int [0..n, 0..n] dist) {for h := 1 to nfor i := 1 to nfor j := 1 to nif (dist[i][j] > dist[i][h] + dist[h][j]) thendist[i][j] := dist[i][h] + dist[h][j];