Dijkstra e Bellman-Ford rispondono alla domanda «quanto dista ogni vertice da questa sorgente?». A volte, però, serve la tabella completa: la distanza tra ogni coppia di vertici. È il caso della classica tabella delle distanze chilometriche stampata sulle vecchie carte stradali, di una matrice dei tempi di viaggio tra i magazzini di un'azienda di logistica, o dell'analisi di una rete aziendale in cui si vuole sapere quanti salti separano ogni coppia di macchine.
L'algoritmo di Floyd-Warshall risolve questo problema con un codice di poche righe, che si scrive a memoria e difficilmente contiene errori.
L'idea: vertici intermedi ammessi, uno alla volta
Numeriamo i vertici da 0 a n − 1. Chiamiamo D_k(i, j) la lunghezza del cammino più corto da i a j che usa come vertici intermedi solo quelli con indice minore di k.
- Con k = 0 non sono ammessi intermedi: D_0(i, j) è il peso dell'arco diretto, oppure infinito se manca.
- Passando da k a k + 1 si ammette anche il vertice k. Il cammino migliore o non lo usa (e resta D_k(i, j)), oppure ci passa una volta sola: da i a k e poi da k a j.
Quindi:
D_{k+1}(i, j) = min( D_k(i, j), D_k(i, k) + D_k(k, j) )
Dopo aver ammesso tutti i vertici si ottengono le distanze minime vere. È un esempio limpido di programmazione dinamica: un problema grande risolto combinando sottoproblemi più piccoli, in un ordine che garantisce che ciò che serve sia già stato calcolato.
Il codice
Una sola matrice basta, aggiornata sul posto:
def floyd_warshall(D):
n = len(D)
for k in range(n):
for i in range(n):
dik = D[i][k]
if dik == float("inf"):
continue
for j in range(n):
if dik + D[k][j] < D[i][j]:
D[i][j] = dik + D[k][j]
return D
L'ordine dei cicli è fondamentale: k deve essere il ciclo più esterno. Scambiarlo con i o j è un errore classico che produce risultati sbagliati senza nessun messaggio d'errore.
La matrice iniziale ha 0 sulla diagonale, il peso dell'arco dove esiste e infinito altrove. Se tra due vertici ci sono più archi, si tiene il più leggero.
Ricostruire i percorsi
Le distanze da sole spesso non bastano: si vuole sapere anche per dove passare. Si mantiene una seconda matrice succ, dove succ[i][j] è il primo vertice da visitare dopo i per andare a j. All'inizio succ[i][j] = j per ogni arco esistente; ogni volta che il passaggio per k migliora la coppia (i, j), si pone succ[i][j] = succ[i][k]. Per ricostruire il percorso si parte da i e si segue succ fino ad arrivare a j.
Pesi negativi e cicli negativi
Floyd-Warshall accetta archi di peso negativo. Se esiste un ciclo negativo, alla fine almeno un elemento della diagonale risulta minore di zero: un vertice «dista da sé stesso» meno di zero. Basta quindi controllare la diagonale per sapere se i risultati sono affidabili.
Costo e limiti
Tre cicli annidati su n vertici: il tempo è proporzionale a n³ e la memoria a n². Qualche ordine di grandezza:
| Vertici | Celle della matrice | Iterazioni del ciclo interno |
|---|---|---|
| 100 | 10 mila | 1 milione |
| 1.000 | 1 milione | 1 miliardo |
| 10.000 | 100 milioni | 1.000 miliardi |
Fino a qualche centinaio di vertici è istantaneo anche in Python; a qualche migliaio diventa pesante senza librerie numeriche; oltre, conviene cambiare approccio. Per grafi grandi e sparsi è molto meglio lanciare Dijkstra da ogni vertice, con un costo complessivo di circa n · (n + m) log n, o l'algoritmo di Johnson se ci sono pesi negativi.
Una variante utile: la chiusura transitiva
Sostituendo la somma con l'«e» logico e il minimo con l'«o» logico, lo stesso schema risponde alla domanda «da i si può raggiungere j?». Si ottiene la chiusura transitiva del grafo, nota anche come algoritmo di Warshall.
Esempi pratici:
- in un sistema di permessi con ruoli che ereditano da altri ruoli, la chiusura dice quali permessi ha effettivamente ogni ruolo;
- in una rete con regole di firewall, dice quali segmenti possono comunicare, anche passando per altri segmenti;
- in un organigramma, dice chi è superiore di chi, a qualunque livello.
In sintesi
- Floyd-Warshall calcola le distanze minime tra tutte le coppie di vertici.
- Ammette i vertici intermedi uno alla volta: è programmazione dinamica.
- Il ciclo su k deve essere il più esterno; il costo è n³ in tempo e n² in memoria.
- Accetta pesi negativi; un valore negativo sulla diagonale segnala un ciclo negativo.
- Con operazioni logiche al posto di somma e minimo calcola la chiusura transitiva.
