Algoritmo di Floyd-Warshall

Algoritmo di Floyd-Warshall
Classe	Algoritmo di ricerca
Struttura dati	Grafo
Caso peggiore temporalmente	O(\|V\|3)
Caso ottimo temporalmente	Ω(\|V\|3)
Caso peggiore spazialmente	Θ(\|V\|2)

L'algoritmo di Floyd-Warshall calcola il cammino minimo per tutte le coppie di un grafo pesato e orientato con una complessità $O(\left|V\right|^{3})$ ^[1]. 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 (A^h-1[i,h] + A^h-1[h,j]) < A^h-1[i,j] allora A^h[i,j] = (A^h-1[i,h] + A^h-1[h,j]) dove h è il piano che stiamo analizzando.

Sotto potete vedere un algoritmo in pseudocodice del procedimento descritto:

Inizializzazione int [0..n, 0..n] dist; for i := 1 to n for j := 1 to n dist[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 n for i := 1 to n for j := 1 to n if (dist[i][j] > dist[i][h] + dist[h][j]) then dist[i][j] := dist[i][h] + dist[h][j];

Ricostruzione dei Cammini Minimi modifica

Al termine della procedura sopra riportata abbiamo solamente ottenuto il peso del cammino minimo tra ogni coppia di nodi, ma non sappiamo ancora quali siano effettivamente i nodi che formano tali cammini. Per ottenere anche il percorso si fa uso di un'ulteriore struttura dati dove memorizziamo, per ogni coppia (i,j) il predecessore di j nel cammino minimo che li collega. In fase di inizializzazione, ovviamente, il predecessore di j nel cammino minimo i → j è i. L'algoritmo si modifica leggermente introducendo questo nuovo elemento:

# inizializzazione
int [0..n, 0..n] dist;
int [0..n, 0..n] pred;
for i := 1 to n
    for j := 1 to n
        dist[i][j] := Weight(i,j);
        pred[i][j] := i;
    endfor
endfor

# floyd-warshall
for h := 1 to n
    for i := 1 to n
        for j := 1 to n
            if (dist[i][j] > dist[i][h] + dist[h][j]) then
                dist[i][j] := dist[i][h] + dist[h][j];
                pred[i][j] := pred[h][j];
            endif
        endfor
    endfor
endfor

Se il cammino minimo tra i e j passa per il nodo h allora il predecessore di j in i→j sarà chiaramente il predecessore di j in h→j.

Una volta ottenuta la struttura dati pred possiamo ricostruire i cammini minimi tra ogni coppia di nodi. Supponiamo di voler ricostruire il cammino minimo P_1,5 e che questo sia 1,3,4,5. Utilizziamo pred in questo modo:

Partiamo da pred[1][5], vale 4
Consideriamo ora pred[1][4], vale 3
Ora pred[1][3], che vale 1: Cammino ricostruito.

Note modifica

^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, The MIT Press, 2009, Sezione 25.2 pag. 693, ISBN 978-0-262-53305-8.

Bibliografia modifica

Eugène L. Lawler, Floyd-Warshall Method, in Combinatorial optimization: networks and matroids. Courier Dover Publications, 2001, pp. 86–92. ISBN 0486414531, ISBN 9780486414539, Google Books. Riportato il 28 febbraio 2011.

Voci correlate modifica

Altri progetti modifica

Wikimedia Commons contiene immagini o altri file su algoritmo di Floyd-Warshall

Collegamenti esterni modifica

(EN) Animazione interattiva dell'algoritmo di Floyd-Warshall, su pms.ifi.lmu.de.
(EN) Implementazione dell'algoritmo di Floyd-Warshall in Java, su algs4.cs.princeton.edu.
(EN) Shortest Paths between every pair of vertices, su graph-magics.com.

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica

[1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, The MIT Press, 2009, Sezione 25.2 pag. 693, ISBN 978-0-262-53305-8.

[1]