L'algoritmo di Floyd–Warshall

I vecchi atlanti stradali avevano in fondo una tabella: la distanza tra ogni coppia di città. Floyd–Warshall è un modo per calcolare una tabella così, ed è uno degli algoritmi più brevi mai scritti: tre cicli, un confronto, e ogni distanza più breve va al suo posto.

Un piccolo grafo i cui archi hanno una lunghezza, accanto a una tabella delle distanze tra ogni coppia di nodi, con una riga e una colonna evidenziate
Un piccolo grafo i cui archi hanno una lunghezza, accanto a una tabella delle distanze tra ogni coppia di nodi, con una riga e una colonna evidenziate

L'idea

L'algoritmo di Dijkstra e Bellman–Ford trovano le distanze più brevi da una sola partenza. Floyd–Warshall le trova da ogni nodo a ogni altro nodo in una volta sola, in una tabella con una riga e una colonna per nodo. Parte da ciò che dicono direttamente gli archi, e poi migliora l'intera tabella ammettendo sempre più nodi come tappe lungo il percorso.

Passo per passo

Riempi la tabella: 0 da ogni nodo a se stesso, la lunghezza dell'arco tra vicini, e infinito altrove. Poi, per ogni nodo k e per ogni coppia i, j: se la distanza da i a k più la distanza da k a j è minore della distanza da i a j, scrivi il numero più piccolo. Questo è tutto l'algoritmo. Nel codice sono tre cicli, con k all'esterno.

Un esempio

Prendi quattro nodi con gli archi A–B di lunghezza 3, B–C 1, A–C 5 e C–D 2. La tabella parte da questi, e da infinito per A–D e B–D. Il turno A non cambia nulla, perché ogni percorso che passa da A è più lungo. Il turno B trova da A a C passando da B: 3 + 1 = 4, meno di 5. Il turno C trova da A a D passando da C: 4 + 2 = 6, e da B a D: 1 + 2 = 3, entrambi i primi percorsi trovati. Il turno D non cambia nulla. La tabella finale: A–B 3, A–C 4, A–D 6, B–C 1, B–D 3, C–D 2.

Perché conta l'ordine dei cicli

La tappa k deve essere il ciclo esterno. Dopo il turno di k, ogni casella è la distanza più breve che usa come tappe solo i primi k nodi, e il turno successivo si basa su questo: un percorso migliore attraverso la nuova tappa è un percorso migliore fino a lei più un percorso migliore da lei, entrambi già giusti. Mettere k in un ciclo interno rompe questa garanzia e può lasciare distanze sbagliate. Aggiornare la tabella sul posto durante un turno è sicuro, perché la riga e la colonna di k non cambiano in quel turno.

Storia e usi

Bernard Roy descrisse il metodo nel 1959. Nel 1962 Stephen Warshall lo pubblicò per la chiusura transitiva, che chiede solo se un nodo può raggiungerne un altro, e Robert Floyd lo pubblicò per i percorsi più brevi. Calcola tabelle delle distanze e tabelle di instradamento, trova il diametro di una rete, dice quali nodi possono raggiungere quali, e con una casella negativa sulla diagonale rivela un ciclo negativo.

Provalo

Apri l'app e premi Passo. Il grafo è da una parte e la tabella dall'altra. Ogni turno evidenzia la riga e la colonna della tappa attuale; ogni passo scrive la distanza più breve di una coppia e contorna le due caselle che sono state sommate. Le caselle cambiate in questo turno sono colorate. Scegli una partenza e un arrivo per vedere il percorso più breve tra i due quando la tabella è completa.

Domande frequenti

Qual è la complessità di Floyd–Warshall?

O(n³) per n nodi, qualunque sia il numero di archi, e O(n²) di memoria per la tabella. È il metodo preferito per grafi piccoli o densi, dove il suo ciclo semplice gira molto veloce.

Floyd–Warshall o Dijkstra da ogni nodo?

Per un grafo denso, o quando gli archi possono essere negativi, Floyd–Warshall è più semplice e circa altrettanto veloce. Per un grafo grande e sparso con archi non negativi, è più veloce eseguire l'algoritmo di Dijkstra da ogni nodo.

Floyd–Warshall è programmazione dinamica?

Sì. Risolve il problema per i percorsi con tappe tra i primi k nodi usando le risposte per i primi k − 1 nodi, e tiene una sola tabella, che sovrascrive man mano.

Che cos'è la chiusura transitiva?

La tabella di quali nodi possono raggiungere quali, senza badare alle distanze. La versione di Warshall dell'algoritmo la calcola con «o» e «e» invece di «min» e «+».

Pronto a provarlo?

Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.

Prova Floyd–Warshall