Passata
Cambiate in questa passata
Archi esaminati

  • Attuale
  • Ha una distanza
  • Arco usato
  • Percorso
  • Ciclo negativo
Un clic su un nodo imposta

Scopri di più sull'algoritmo di Bellman–Ford

Algoritmo di Bellman–Ford

L'algoritmo di Dijkstra non funziona quando un arco ha lunghezza negativa, come una strada che ti paga un pedaggio invece di fartelo pagare. L'algoritmo di Bellman–Ford sì: esamina semplicemente ogni arco più e più volte finché nulla migliora, e sa perfino dire quando un ciclo fa scendere le distanze all'infinito. Fai clic su un nodo per partire da lì e procedi passata per passata. Premi Avvia per guardare la ricerca, oppure Passo e Indietro per procedere un passo alla volta. Trascina il cursore dei passi per saltare dove vuoi. Ogni arco è a senso unico, come mostra la sua freccia, e il numero sopra è la sua lunghezza, che può essere negativa. Fai clic su un nodo per farne la partenza; passa il clic su Arrivo e fai clic su un altro nodo per vedere alla fine il percorso più breve fino a lì. Il numero su ogni nodo è la sua distanza finora. Spunta Aggiungi un ciclo negativo per vedere come Bellman–Ford ne trova uno. Nuovo grafo crea un altro grafo; scegli quanti nodi e archi deve avere. Con il riquadro selezionato, le frecce vanno avanti e indietro di un passo, la barra spaziatrice avvia e mette in pausa, e Home e Fine saltano all'inizio e alla fine.

Come funziona

  1. Fai clic su un nodo per farne la partenza. Per vedere un percorso alla fine, passa il clic su Arrivo e fai clic su un altro nodo.
  2. Premi Avvia, oppure usa Passo e Indietro per procedere un passo alla volta. Trascina il cursore dei passi per saltare in qualsiasi punto.
  3. Spunta Aggiungi un ciclo negativo per vedere Bellman–Ford trovarne uno. Nuovo grafo crea un altro grafo da provare.

Come funziona Bellman–Ford

Dai alla partenza distanza 0 e a tutti gli altri nodi infinito. Poi fai le passate: in ogni passata, esamina una volta ogni arco u → v. Se u ha una distanza e dist(u) più la lunghezza dell'arco è minore di dist(v), abbassa dist(v) e ricorda u come via per arrivarci. Dopo la passata k si conosce ogni percorso più breve che usa al massimo k archi. Un percorso più breve visita ogni nodo al massimo una volta, quindi ha al massimo n − 1 archi, e bastano sempre n − 1 passate. Se un'intera passata non cambia nulla, la ricerca può fermarsi prima.

Trovare un ciclo negativo

Se gli archi di un ciclo sommano a meno di zero, fare un altro giro rende sempre un percorso più corto, quindi non esiste nessun percorso più breve. Bellman–Ford se ne accorge: dopo n − 1 passate, una passata in più non dovrebbe cambiare nulla. Se un arco si può ancora rilassare, dalla partenza si raggiunge un ciclo negativo, e risalendo i nodi ricordati a partire da quell'arco si arriva dentro il ciclo. Nell'app il ciclo è disegnato in rosso.

Domande frequenti

Che cos'è l'algoritmo di Bellman–Ford?

Un algoritmo che trova i percorsi più brevi da una partenza a tutti gli altri nodi in un grafo i cui archi possono avere lunghezze negative. Rilassa ogni arco in passate ripetute, e segnala un ciclo negativo se se ne può raggiungere uno dalla partenza.

Perché l'algoritmo di Dijkstra fallisce con archi negativi?

Dijkstra rende definitiva la distanza di un nodo appena è il più vicino in coda. Un arco negativo trovato più tardi può ancora riportare a quel nodo per una via più breve, quindi la distanza definitiva può essere sbagliata. Bellman–Ford non rende mai definitiva una distanza troppo presto; continua a esaminare ogni arco.

Perché n − 1 passate?

Un percorso più breve non ha mai bisogno di visitare un nodo due volte, quindi ha al massimo n − 1 archi. Ogni passata allunga i percorsi più brevi noti di almeno un arco, quindi dopo n − 1 passate sono stati trovati tutti.

Quanto è veloce Bellman–Ford?

Ogni passata esamina tutti gli E archi e ci sono al massimo V − 1 passate, quindi il lavoro cresce come V × E. È più lento dell'algoritmo di Dijkstra, ed è per questo che Bellman–Ford si usa quando gli archi possono essere negativi.

Il mio grafo viene inviato da qualche parte?

No. Il grafo viene creato e visitato nel tuo browser, e le tue ultime impostazioni restano nella memoria locale di questo browser.

Pronto a provarlo?

Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.

Vai all'editor