Bellman-Ford e archi negativi
Gestire i valori negativi e rilevare i cicli
Bellman-Ford e archi negativi è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 3 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.
Quando Dijkstra fallisce
Dijkstra presume che una distanza estratta sia definitiva, ma un arco negativo può successivamente rendere più economico un percorso. Per questo fallisce.
Entra in scena Bellman-Ford
Bellman-Ford gestisce i pesi negativi degli archi. È più lento di Dijkstra, ma affidabile nei casi in cui la logica greedy non può essere applicata.
L'operazione fondamentale
Ripete il rilassamento di ogni arco: se dist[u] più il peso dell'arco è minore di dist[v], aggiorna dist[v] con quel valore più piccolo.
if dist[u] + w < dist[v]:
dist[v] = dist[u] + wQuanti cicli eseguire
Un cammino minimo usa al massimo V meno 1 archi, quindi sono sufficienti V-1 cicli di rilassamento di tutti gli archi per determinare tutte le distanze.
for _ in range(n - 1):
relax_all_edges()Inizializzare le distanze
Imposti ogni distanza a infinito, tranne quella della sorgente, che deve essere zero, esattamente come in Dijkstra.
dist = [float('inf')] * n
dist[src] = 0Un passaggio completo
A ogni passaggio percorra una volta l'intero elenco degli archi e rilassi ogni arco. I miglioramenti si propagano verso l'esterno di un arco per passaggio.
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + wPerché V-1 è sufficiente
Dopo k passaggi, tutti i cammini minimi che usano k archi sono corretti. Dopo V-1 passaggi, ogni cammino minimo semplice è completo.
Il passaggio aggiuntivo
Esegua un altro passaggio. Se una distanza diminuisce ancora, qualcosa continua a diventare più conveniente: questo segnala un ciclo negativo.
Rilevare i cicli negativi
Un ciclo negativo significa che non esiste alcun cammino minimo finito, perché è possibile percorrerlo indefinitamente per ridurre il costo senza limite.
for u, v, w in edges:
if dist[u] + w < dist[v]:
return 'negative cycle'Il tempo di esecuzione
Si rilassano E archi per V passaggi, quindi Bellman-Ford richiede O(V * E), un costo adeguato per grafi piccoli o medi.
Dijkstra o Bellman-Ford
Scelga Dijkstra con pesi non negativi quando serve velocità. Scelga Bellman-Ford quando compaiono valori negativi o deve rilevare un ciclo problematico.
Verifica rapida
Dopo V-1 passaggi, una distanza diminuisce ancora durante un passaggio aggiuntivo. Che cosa significa?
Riepilogo: Bellman-Ford
Rilassi tutti gli archi per V-1 passaggi, poi ne esegua un altro per rilevare i cicli negativi. È un algoritmo O(V*E), ma funziona dove Dijkstra non può. ✅
Domande Frequenti
La lezione «Bellman-Ford e archi negativi» è gratuita?
Sì — il testo completo di «Bellman-Ford e archi 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 archi negativi»?
Gestire i valori negativi e rilevare i cicli 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 3 di 4.
Quanto tempo richiede la lezione «Bellman-Ford e archi 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
- Dijkstra con un heap
- BFS 0-1 con una Deque
- Bellman-Ford e archi negativi
- Floyd-Warshall per tutte le coppie