Floyd-Warshall: cammini minimi tra tutte le coppie

Floyd-Warshall calcola i cammini minimi tra ogni coppia di nodi in un grafo pesato, inclusi i grafi con archi dal peso negativo, ma non quelli con cicli negativi. Eseguire Dijkstra da ogni sorgente richiede O(V × (V+E) log V); Floyd-Warshall richiede O(V³) indipendentemente dalla densità degli archi. Per i grafi densi con V ≤ 500, Floyd-Warshall è spesso più semplice e ha prestazioni comparabili.

L'intuizione di Floyd-Warshall: dp[i][j][k] = cammino minimo da i a j usando solo i nodi {0, 1, ..., k} come intermediari. Il cammino minimo usa il nodo k come nodo intermedio oppure non lo usa. Se lo usa: dp[i][j][k] = dp[i][k][k-1] + dp[k][j][k-1]. Altrimenti: dp[i][j][k] = dp[i][j][k-1]. Poiché la terza dimensione procede solo in avanti, può essere eliminata: si aggiorna direttamente in memoria.

Si inizi con una matrice V×V: dist[i][i] = 0 per la distanza da un nodo a sé stesso, dist[i][j] = weight per gli archi diretti e dist[i][j] = inf per le coppie non collegate da un arco. Si scorrano quindi tutti i nodi intermedi k, aggiornando le coppie (i, j). Il ciclo esterno su k deve venire per primo, così da costruire correttamente i cammini attraverso un insieme crescente di nodi intermedi consentiti.

Si segua Floyd-Warshall su un grafo con 4 nodi. Dopo aver elaborato ciascun nodo intermedio k, la matrice si completa con cammini più brevi che passano per il nodo k. L'algoritmo gestisce naturalmente più passaggi costruendo progressivamente i cammini minimi.

Dopo aver eseguito Floyd-Warshall, si controlli la diagonale principale: se un valore dist[i][i] < 0, esiste un ciclo negativo che passa per il nodo i. Questo accade perché un ciclo negativo consente di raggiungere i partendo da i con un costo negativo. Se non esiste alcun ciclo negativo, tutte le voci della diagonale rimangono pari a 0.

Per ricostruire il cammino effettivo da i a j, si mantenga una matrice next[i][j]: inizialmente next[i][j] = j per gli archi diretti. Quando si aggiorna il cammino passando per il nodo intermedio k, si imposti next[i][j] = next[i][k]. Per recuperare il cammino, si inizi da i e si seguano i puntatori next fino a raggiungere j. Ciò aggiunge O(V²) di memoria e O(V) per ogni ricostruzione del cammino.

Una variante più semplice: la Chiusura transitiva risponde alla domanda: il nodo j è raggiungibile dal nodo i? per tutte le coppie. Si sostituiscano le distanze con valori booleani: reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j]). Si tratta di Floyd-Warshall con l'operatore booleano OR al posto dell'addizione e del minimo. Si inizializzi reach[i][i] = True e reach[i][j] = True per gli archi diretti.

Floyd-Warshall: O(V³) di tempo, O(V²) di spazio. Per i grafi densi (E ≈ V²) con V ≤ 300, è più veloce che eseguire Dijkstra V volte, anch'esso O(V³) in tal caso. Per i grafi sparsi con V = 1000 e E = 3000, eseguire V volte Dijkstra ha un costo O(V×E×log V) ≈ 33M, mentre Floyd-Warshall ha un costo O(V³) = 10⁹: in questo caso vince Dijkstra. È importante sapere quando ciascun algoritmo è appropriato.

Imposti tutti i pesi degli archi su 1 (oppure utilizzi una matrice di adiacenza booleana con Floyd-Warshall, usando l'addizione al posto del minimo): dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). In questo modo si calcola il numero minimo di passaggi tra tutte le coppie: il risultato di una BFS per tutte le coppie, ottenuto però con un'unica esecuzione di Floyd-Warshall in O(V³).

Floyd-Warshall compare nei colloqui per domande che riguardano: (1) le distanze tra tutte le coppie in un grafo piccolo, (2) la verifica dell'esistenza di un ciclo con peso totale negativo, (3) il calcolo dei percorsi minimi nei problemi di propagazione dei vincoli e (4) i problemi che richiedono esplicitamente soluzioni O(V³) con V ≤ 200. Menzioni sempre la struttura a tre cicli e il requisito dell'assenza di cicli negativi affinché il risultato sia corretto.

Per i grafi non orientati, aggiunga entrambe le direzioni per ogni arco: dist[u][v] = dist[v][u] = weight. Il resto dell'algoritmo è identico. La matrice risultante è simmetrica: dist[i][j] == dist[j][i] per tutte le coppie. Durante l'inizializzazione, faccia attenzione a non assegnare accidentalmente archi orientati: gli archi non orientati devono essere aggiunti in entrambe le direzioni alla matrice iniziale prima di eseguire i tre cicli.

Verifichi la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.

In questa lezione ha imparato che: Floyd-Warshall calcola i percorsi minimi tra tutte le coppie con tre cicli annidati e la ricorrenza dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]), i cicli negativi possono essere rilevati verificando se, al termine, esiste un dist[i][i] < 0 e l'algoritmo richiede O(V³) tempo e O(V²) spazio. Ora riprenderemo le applicazioni dei percorsi minimi con Network Delay Time e le tecniche di ricostruzione dei percorsi.