Algoritmo di Floyd-Warshall

Da Wikipedia, l'enciclopedia libera.

L'algoritmo di Floyd-Warshall calcola lo shortest path per tutte le coppie di un grafo pesato e orientato con una complessità O(N³).

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.

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.

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:

function fw(int[0..n,0..n] graph) {
    // Initialization
    var int[0..n,0..n] dist := graph
    var int[0..n,0..n] pred
    for i from 0 to n
        for j from 0 to n
            if dist[i,j] > 0
                pred[i,j] := i
    // Main loop of the algorithm
    for k from 0 to n
        for i from 0 to n
            for j from 0 to n
                if dist[i,j] > dist[i,k] + dist[k,j]
                    dist[i,j] = dist[i,k] + dist[k,j]
                    pred[i,j] = pred[k,j]
    return dist
}