Floyd-Warshall per tutte le coppie

A volte serve il cammino minimo tra ogni coppia di nodi, non solo da una singola sorgente. Questo è il problema dei cammini tra tutte le coppie.

Floyd-Warshall riempie una tabella completa delle distanze per tutte le coppie con tre semplici cicli annidati e quasi nessuna inizializzazione.

Utilizzi una matrice in cui dist[i][j] è il costo minimo conosciuto da i a j. La inizializzi usando gli archi diretti forniti.

Ogni nodo raggiunge sé stesso gratuitamente, quindi imposti a zero la diagonale dist[i][i] prima di iniziare i rilassamenti.

La tecnica consiste nel consentire ai cammini di passare attraverso un nodo intermedio k, quindi verificare se passare da k è più economico che procedere direttamente.

Il ciclo esterno è k, il punto intermedio scelto. I cicli interni su i e j provano ogni coppia rispetto a quel punto intermedio.

Per ogni coppia, rilassi passando da k: se il percorso da i a k e poi a j è più breve, aggiorni dist[i][j] con il costo complessivo.

Quando k termina, tutte le coppie possono usare nodi intermedi fino a k. Mettere k all'esterno mantiene corretta questa garanzia.

Floyd-Warshall accetta gli archi negativi, ma non i cicli negativi. Un ciclo negativo lascia una voce della diagonale minore di zero.

Tre cicli su n nodi richiedono O(n^3) tempo e O(n^2) spazio; è pratico solo quando n rimane nell'ordine di qualche centinaio.

Scelga Floyd-Warshall quando il grafo è piccolo e denso e servono davvero tutte le distanze tra le coppie, non quelle da una sola sorgente.

Inizializzi una matrice, imposti a zero la diagonale, quindi esegua i cicli k, i, j e rilassi passando da k. Cammini minimi tra tutte le coppie in O(n^3). 🧮