Bellman-Ford e cicli negativi
Esegua n-1 passaggi di rilassamento su tutti gli archi, rilevi i cicli negativi con un passaggio finale e spieghi perché Dijkstra non funziona con archi di peso negativo.
Bellman-Ford e cicli negativi è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 2 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Perché esiste Bellman-Ford
Bellman-Ford risolve il problema dei cammini minimi da una singola sorgente, come Dijkstra, ma gestisce i pesi negativi degli archi. Inoltre rileva i cicli negativi: cicli il cui peso totale è negativo, per i quali è impossibile definire un cammino minimo finito che li attraversi. Sebbene sia più lento di Dijkstra, Bellman-Ford è la scelta corretta ogni volta che il grafo può contenere archi con peso negativo.
Rilassamento: l'operazione fondamentale
Bellman-Ford si basa su una singola operazione: il rilassamento. Rilassare l'arco (u, v, w) significa: se dist[u] + w < dist[v], aggiornare dist[v] = dist[u] + w. Si rilassano ripetutamente tutti gli archi. L'intuizione fondamentale è che ogni cammino minimo ha al massimo V-1 archi in un grafo privo di cicli negativi. Pertanto, V-1 passaggi di rilassamento su tutti gli archi sono sufficienti per trovare tutti i cammini minimi.
Implementazione di Bellman-Ford
Si rappresenti il grafo come una lista di archi [(u, v, weight)]. Si inizializzi dist[source] = 0 e tutti gli altri valori a inf. Si eseguano V-1 passaggi, rilassando tutti gli archi a ogni passaggio. Un aggiornamento che si verifica ancora durante il V-esimo passaggio indica un ciclo negativo.
def bellman_ford(V, edges, source):
dist = [float('inf')] * V
dist[source] = 0
# V-1 relaxation passes
for _ in range(V - 1):
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# V-th pass: detect negative cycle
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
return None # negative cycle exists
return dist
edges = [(0,1,4),(0,2,5),(1,2,-3),(2,3,1)]
print(bellman_ford(4, edges, 0)) # [0, 4, 1, 2]Perché V-1 passaggi sono sufficienti
Un cammino minimo in un grafo privo di cicli negativi visita ogni nodo al massimo una volta, quindi contiene al massimo V-1 archi. Dopo il primo passaggio, i cammini minimi con 1 arco sono ottimali. Dopo il secondo passaggio, sono ottimali i cammini minimi con 2 archi. Dopo V-1 passaggi, sono stati trovati tutti i cammini minimi, che usano al massimo V-1 archi. Se durante il passaggio V viene ancora aggiornata una distanza, il grafo contiene un ciclo negativo raggiungibile dalla sorgente.
Rilevamento dei cicli negativi
Dopo V-1 passaggi, si esegua un passaggio aggiuntivo su tutti gli archi. Se un arco (u, v, w) soddisfa dist[u] + w < dist[v], allora esiste un ciclo negativo e il cammino minimo verso alcuni nodi è -infinity. Tra le applicazioni reali vi sono il rilevamento di opportunità di arbitraggio negli scambi valutari, attraverso cicli negativi nei grafi con pesi logaritmici, e il rilevamento di incoerenze nei sistemi di vincoli.
def has_negative_cycle(V, edges, source):
dist = [float('inf')] * V
dist[source] = 0
for _ in range(V - 1):
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# Nth pass
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
return True # negative cycle detected
return False
# Negative cycle: 1->2->3->1 with weights -1,-1,1 (sum=-1)
edges_neg = [(0,1,1),(1,2,-1),(2,3,-1),(3,1,1)]
print(has_negative_cycle(4, edges_neg, 0)) # TrueConfronto tra Dijkstra e Bellman-Ford
Dijkstra: O((V+E) log V), richiede pesi non negativi, approccio greedy. Bellman-Ford: O(V × E), gestisce i pesi negativi e rileva i cicli negativi. Per la maggior parte dei problemi da colloquio con pesi non negativi, si preferisce Dijkstra. Quando compaiono pesi negativi, ad esempio in problemi che chiedono di trovare il cammino minimo con archi dal costo negativo o di rilevare un arbitraggio, la risposta è Bellman-Ford. Per i grafi densi, il caso peggiore O(V³) di Bellman-Ford è paragonabile a quello di Floyd-Warshall.
Applicazione: voli più economici con Bellman-Ford
Voli più economici con al massimo K scali (LeetCode 787) può essere risolto con una versione modificata di Bellman-Ford: si eseguano esattamente k+1 passaggi di rilassamento, poiché k scali equivalgono a k+1 archi. Si usi una copia delle distanze del passaggio precedente per assicurarsi di non usare più archi di quelli consentiti in un singolo passaggio; altrimenti un singolo passaggio potrebbe concatenare più archi.
def findCheapestPrice_bf(n, flights, src, dst, k):
dist = [float('inf')] * n
dist[src] = 0
for _ in range(k + 1): # k stops = k+1 edges
temp = dist[:] # copy to avoid using updated dist in same pass
for u, v, w in flights:
if dist[u] != float('inf') and dist[u] + w < temp[v]:
temp[v] = dist[u] + w
dist = temp
return dist[dst] if dist[dst] != float('inf') else -1
print(findCheapestPrice_bf(4,[[0,1,100],[1,2,100],[0,2,500]],0,2,1)) # 200SPFA: ottimizzazione basata su una coda
Shortest Path Faster Algorithm (SPFA) è una versione ottimizzata di Bellman-Ford che rilassa nuovamente solo gli archi dei nodi la cui distanza è appena stata aggiornata, usando una coda. Il caso medio è O(E), ma il caso peggiore rimane O(V × E). SPFA è raramente richiesto nei colloqui, ma può essere menzionato come ottimizzazione quando Bellman-Ford è troppo lento sui grafi sparsi. Python non dispone di un'implementazione SPFA integrata, ma è semplice implementarla con collections.deque.
Rilevamento dell'arbitraggio valutario
Una classica applicazione di Bellman-Ford: dati i tassi di cambio tra valute, si rilevi se è possibile effettuare un arbitraggio, cioè un ciclo in cui, convertendo le valute, si ottiene più di quanto si possedesse inizialmente. Si trasformino i tassi calcolandone il logaritmo negativo. Arbitraggio = un ciclo con peso logaritmico totale negativo = un ciclo negativo rilevabile da Bellman-Ford. In questo modo i problemi finanziari del mondo reale vengono ricondotti all'algoritmo standard.
import math
def has_arbitrage(rates):
n = len(rates)
# Transform: -log(rate) converts product to sum
log_rates = [[-math.log(rates[i][j]) for j in range(n)] for i in range(n)]
edges = [(i,j,log_rates[i][j]) for i in range(n) for j in range(n) if i != j]
dist = [float('inf')] * n
dist[0] = 0
for _ in range(n - 1):
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
for u, v, w in edges:
if dist[u] + w < dist[v]:
return True # arbitrage!
return FalseOttimizzazione con terminazione anticipata
Se durante un passaggio completo su tutti gli archi non viene aggiornata alcuna distanza, i passaggi successivi non aggiorneranno nulla; si può quindi terminare in anticipo. Questa ottimizzazione riduce la complessità nel caso migliore a O(E), quando il grafo è già ottimale dopo pochi passaggi. Si aggiunga un flag updated = False all'inizio di ogni passaggio; se rimane False al termine del passaggio, si interrompa immediatamente.
def bellman_ford_optimised(V, edges, source):
dist = [float('inf')] * V
dist[source] = 0
for _ in range(V - 1):
updated = False
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
updated = True
if not updated:
break # no more improvements possible
return distBellman-Ford su grafi con liste di adiacenza
Quando il grafo è fornito come lista di adiacenza invece che come lista di archi, si converta prima in una lista di archi oppure si scorrano tutte le voci delle liste di adiacenza come archi. Per V=1000 e E=5000, V-1=999 passaggi, ognuno dei quali esamina 5000 archi, producono 4,995,000 operazioni, un numero ampiamente compatibile con i limiti di tempo. Per i grafi molto densi (E ≈ V²), il caso peggiore O(V³) coincide con quello di Floyd-Warshall, quindi la scelta dipende dal contesto.
from collections import defaultdict
def bellman_ford_adj(V, adj, source):
# Convert adjacency list to edge list
edges = [(u, v, w) for u in range(V) for v, w in adj[u]]
dist = [float('inf')] * V
dist[source] = 0
for _ in range(V - 1):
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
return distVerifica rapida
Verifichi la propria comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep presentati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato che: Bellman-Ford rilassa tutti gli archi V-1 volte per gestire gli archi dal peso negativo, un V-esimo passaggio di rilassamento che trova ancora dei miglioramenti indica un ciclo negativo e l'algoritmo richiede O(V × E), rispetto a O((V+E) log V) per Dijkstra. Nel prossimo argomento tratteremo Floyd-Warshall per trovare i cammini minimi tra tutte le coppie in un singolo calcolo O(V³).
Domande Frequenti
La lezione «Bellman-Ford e cicli negativi» è gratuita?
Sì — il testo completo di «Bellman-Ford e cicli negativi» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Bellman-Ford e cicli negativi»?
Esegua n-1 passaggi di rilassamento su tutti gli archi, rilevi i cicli negativi con un passaggio finale e spieghi perché Dijkstra non funziona con archi di peso negativo. Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 2 di 4.
Quanto tempo richiede la lezione «Bellman-Ford e cicli negativi»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Algoritmo di Dijkstra con coda di priorità
- Bellman-Ford e cicli negativi
- Floyd-Warshall: cammini minimi tra tutte le coppie
- Network Delay Time e ricostruzione del percorso