L'algoritmo di Dijkstra è veloce ed elegante, ma ha un limite netto: tutti gli archi devono avere peso non negativo. Quando questa condizione non vale, serve un approccio più paziente. L'algoritmo di Bellman-Ford è più lento, ma accetta pesi negativi e, soprattutto, sa riconoscere la situazione in cui il problema stesso non ha senso: la presenza di un ciclo negativo.
Quando compaiono pesi negativi
Una lunghezza stradale non è mai negativa, ma molti problemi modellati come cammini minimi sì:
- guadagni e costi: in una sequenza di operazioni alcune costano e altre fanno guadagnare; un guadagno si rappresenta come peso negativo;
- vincoli di differenza: sistemi di vincoli del tipo «l'evento B deve avvenire al massimo 3 ore dopo A» si traducono in un grafo dove alcuni archi hanno peso negativo, e le soluzioni sono date proprio dalle distanze minime;
- tassi di cambio: passando per logaritmi, come vedremo, la ricerca di opportunità di arbitraggio diventa una ricerca di cicli negativi.
L'idea: rilassare tutto, più volte
Bellman-Ford non sceglie un ordine furbo in cui elaborare i vertici. Rilassa tutti gli archi, poi lo fa di nuovo, e ancora, per n − 1 volte in tutto.
def bellman_ford(n, archi, s):
INF = float("inf")
dist = [INF] * n
dist[s] = 0
for _ in range(n - 1):
cambiato = False
for u, v, w in archi:
if dist[u] != INF and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
cambiato = True
if not cambiato:
break
for u, v, w in archi:
if dist[u] != INF and dist[u] + w < dist[v]:
raise ValueError("ciclo negativo raggiungibile dalla sorgente")
return dist
Perché proprio n − 1 passate? Se non ci sono cicli negativi, un cammino minimo non ripete vertici, quindi usa al massimo n − 1 archi. Dopo la prima passata sono corrette tutte le distanze dei vertici raggiungibili con un arco lungo un cammino minimo; dopo la seconda quelle con due archi; dopo la k-esima quelle con k archi. Dopo n − 1 passate, tutte.
La variabile cambiato è un'ottimizzazione pratica importante: se in una passata nessuna stima migliora, le successive non cambierebbero nulla e si può uscire subito. Su molti grafi reali l'algoritmo termina dopo poche passate.
Il controllo finale: cicli negativi
Un ciclo negativo è un ciclo la cui somma dei pesi è minore di zero. Se è raggiungibile dalla sorgente, percorrerlo una volta in più abbassa sempre il costo, quindi la «distanza minima» non esiste: si può scendere all'infinito.
Bellman-Ford lo scopre con una passata supplementare. Se dopo n − 1 passate qualche arco si può ancora rilassare, c'è per forza un ciclo negativo. Seguendo all'indietro i puntatori al predecessore dal vertice migliorato, per n passi, si finisce sicuramente dentro il ciclo, e da lì lo si può ricostruire per mostrarlo.
Un esempio: l'arbitraggio sui cambi
Supponiamo di conoscere i tassi di cambio tra alcune valute. Un arbitraggio è una sequenza di conversioni che, partendo da una valuta, ritorna alla stessa con più denaro di prima: il prodotto dei tassi lungo il ciclo è maggiore di 1.
Il trucco è trasformare i prodotti in somme con i logaritmi. Si dà a ogni arco da X a Y il peso −log(tasso X→Y). Il prodotto dei tassi su un ciclo è maggiore di 1 esattamente quando la somma dei logaritmi è positiva, cioè quando la somma dei pesi è negativa. Cercare un arbitraggio significa quindi cercare un ciclo negativo, ed è un compito su misura per Bellman-Ford.
Nella realtà commissioni, spread e latenza riducono queste opportunità, ma il modello resta un esempio limpido di come una trasformazione dei pesi riconduca un problema nuovo a un algoritmo noto.
Costo e confronto con Dijkstra
Ogni passata esamina tutti gli m archi e le passate sono al massimo n − 1, quindi il costo nel caso peggiore è proporzionale a n · m. È molto più di Dijkstra, che costa circa (n + m) log n.
| Aspetto | Dijkstra | Bellman-Ford |
|---|---|---|
| Pesi negativi | no | sì |
| Rileva cicli negativi | no | sì |
| Costo tipico | (n + m) log n | n · m |
| Struttura dati | coda di priorità | lista di archi |
La regola pratica è semplice: se i pesi sono tutti non negativi si usa Dijkstra; altrimenti Bellman-Ford, o una sua variante.
Varianti e usi
- Coda dei vertici modificati: invece di rilassare tutti gli archi a ogni passata, si rielaborano solo i vertici la cui stima è cambiata. Nei casi medi accelera molto, anche se il caso peggiore resta lo stesso.
- Algoritmo di Johnson: per calcolare i cammini minimi tra tutte le coppie in grafi sparsi con pesi negativi, si usa una volta Bellman-Ford per «ripesare» gli archi rendendoli non negativi, poi si lancia Dijkstra da ogni vertice.
- Instradamento distance-vector: alcuni protocolli di rete storici, come RIP, si basano su una versione distribuita della stessa idea: ogni router comunica ai vicini le proprie stime e le aggiorna in base a quelle ricevute.
In sintesi
- Bellman-Ford calcola cammini minimi da una sorgente anche con pesi negativi.
- Rilassa tutti gli archi per n − 1 passate, fermandosi prima se nulla cambia.
- Una passata in più rivela i cicli negativi, in cui la distanza minima non esiste.
- Con pesi −log(tasso), la ricerca di arbitraggi diventa ricerca di cicli negativi.
- Costa n · m: va usato quando i pesi negativi ci sono davvero.
