1. Il problema

Dato un grafo orientato e pesato G = (V, E), vogliamo una matrice D in cui D[i][j] è il costo minimo da i a j. La diagonale vale 0 se non esistono cicli negativi; D[i][j] = +∞ quando j non è raggiungibile da i. Se ci sono più archi i → j, nell’inizializzazione si prende il peso minore.

Per una sola sorgente, parti dalla guida precedente. Per tutte le coppie, la struttura del grafo conta: Floyd–Warshall visita tutti i tripletti di vertici, mentre Johnson sfrutta la sparsità degli archi.

2. Un grafo che useremo per entrambi

Consideriamo i quattro vertici A, B, C, D e gli archi orientati seguenti. B → C ha peso negativo, ma il ciclo B → C → D → B pesa −2 + 2 + 1 = 1: non è negativo.

Da A a D, per esempio, il percorso A → B → C → D pesa 3 − 2 + 2 = 3; quello A → B → D pesa 8. Da C ad A non esiste alcun percorso.

3. Floyd–Warshall: aggiungere intermedi

Numeriamo i vertici. D^(k)[i][j] è il costo minimo da i a j usando come vertici interni solo i primi k vertici. Il cammino ottimo o evita k, oppure passa per k: in quest’ultimo caso combina un percorso i → k e uno k → j.

Inizializziamo la diagonale a 0, gli archi ai loro pesi e le altre celle a +∞. Il ciclo su k deve essere esterno: a ogni fase si ammette esattamente un nuovo possibile intermedio. Le celle possono essere aggiornate nella stessa matrice se non ci sono cicli negativi.

per ogni i, j: D[i][j] = 0 se i = j; altrimenti +∞
per ogni arco i → j di peso w: D[i][j] = min(D[i][j], w)
per ogni vertice k:
    per ogni vertice i:
        per ogni vertice j:
            se D[i][k] e D[k][j] sono finiti:
                D[i][j] = min(D[i][j], D[i][k] + D[k][j])

Nell’esempio, usando B come intermedio A → C scende da 8 a 3 + (−2) = 1. Usando poi C, A → D scende da 8 a 1 + 2 = 3. Infine D permette C → B con costo 2 + 1 = 3.

Per ricostruire i percorsi, conserva anche next[i][j], il primo vertice dopo i sul cammino verso j. All’inizio next[i][j] = j per un arco diretto; quando un passaggio per k migliora D[i][j], poni next[i][j] = next[i][k].

4. Johnson: riponderare e ripetere Dijkstra

Johnson è adatto a grafi sparsi con possibili archi negativi ma senza cicli negativi. Aggiunge un vertice artificiale q e archi q → v di peso 0 verso tutti i vertici originali. Esegue Bellman–Ford da q: la distanza ottenuta h(v) è un potenziale. Se Bellman–Ford rileva un ciclo negativo, l’algoritmo si ferma.

La disuguaglianza segue da Bellman–Ford: h(v) ≤ h(u) + w(u,v). I pesi riponderati sono quindi adatti a Dijkstra. La correzione non cambia quali percorsi sono ottimi: lungo ogni cammino da s a t, i potenziali intermedi si cancellano e il nuovo peso è quello originale più h(s) − h(t).

aggiungi q e gli archi q → v di peso 0
h = Bellman–Ford(G con q, sorgente q)
se esiste un ciclo negativo: interrompi
per ogni arco u → v: w′(u,v) = w(u,v) + h(u) − h(v)
per ogni sorgente s originale:
    δ′ = Dijkstra(G con pesi w′, sorgente s)
    per ogni t raggiungibile: D[s][t] = δ′(s,t) − h(s) + h(t)
    per ogni t irraggiungibile: D[s][t] = +∞

Nel grafo di esempio, Bellman–Ford da q dà h(A) = 0, h(B) = 0, h(C) = −2, h(D) = 0. Gli archi riponderati A → B, A → C, B → C, B → D, C → D, D → B hanno rispettivamente pesi 3, 10, 0, 5, 0, 1: nessuno è negativo.

Dijkstra da A trova δ′(A,C) = 3 tramite B; riportando il potenziale, D[A][C] = 3 − 0 + (−2) = 1. Da D trova δ′(D,C) = 1 tramite B; il costo originale è 1 − 0 + (−2) = −1. Sono le stesse celle della matrice di Floyd–Warshall.

5. Cicli negativi

Floyd–Warshall segnala un ciclo negativo se, al termine, qualche D[k][k] < 0. Per una coppia (i, j), il valore è −∞ se esiste un tale k con D[i][k] e D[k][j] finiti: si può raggiungere il ciclo e poi j. Non basta controllare la sola diagonale quando si vogliono distinguere tutte le coppie coinvolte.

Johnson trova qualsiasi ciclo negativo del grafo perché q raggiunge ogni vertice. In tal caso non produce una matrice ordinaria di distanze finite. Se serve conoscere le coppie ancora valide, si può usare la verifica di raggiungibilità sui cicli negativi dopo Floyd–Warshall.

Nell’esempio, cambiare D → B da 1 a −1 rende B → C → D → B un ciclo di peso −1. A → D diventa −∞; C → A resta +∞ perché A non è raggiungibile da C.

6. Scelta e complessità

I limiti per Johnson e Dijkstra assumono un grafo semplice, liste di adiacenza e una coda binaria; includono la matrice di output. Johnson esegue anche un Bellman–Ford iniziale, il cui costo è assorbito dal limite mostrato. Se le righe vengono consumate una alla volta, la memoria ausiliaria di Johnson scende a O(|V| + |E|). Floyd–Warshall usa O(|V|²) anche con la matrice dei prossimi vertici.

7. Errori ed esercizi

• Invertire i cicli di Floyd–Warshall: k deve rimanere il ciclo esterno, perché identifica gli intermedi consentiti in ciascuna fase.
• Usare Dijkstra sui pesi originali negativi in Johnson: prima serve la riponderazione ottenuta dai potenziali.
• Dimenticare la correzione finale: le distanze sui pesi riponderati non sono le distanze originali.
• Interpretare +∞ come ciclo negativo: significa irraggiungibilità; −∞ descrive invece un costo che scende senza limite.