L'algoritmo di Bellman–Ford

Alcuni problemi di percorso più breve hanno archi che rendono un percorso più economico: un rimborso, un tratto in discesa, un tasso di cambio a tuo favore. L'algoritmo di Dijkstra non sa gestirli. L'algoritmo di Bellman–Ford sì, scambiando l'astuzia con la pazienza.

Un grafo con frecce a senso unico, alcuni archi negativi, le distanze trovate finora sui nodi, e un ciclo negativo disegnato in rosso
Un grafo con frecce a senso unico, alcuni archi negativi, le distanze trovate finora sui nodi, e un ciclo negativo disegnato in rosso

L'idea

Ogni algoritmo di percorso più breve si basa su una sola mossa, rilassare un arco: se andare fino a u e poi lungo l'arco u → v è più breve della miglior via nota fino a v, si usa quella. L'algoritmo di Dijkstra rilassa ogni arco una volta, in un ordine astuto che funziona solo se nessun arco è negativo. Bellman–Ford non fa questa ipotesi. Rilassa ogni arco, in un qualsiasi ordine fisso, più e più volte, finché le distanze smettono di cambiare.

Passo per passo

Dai alla partenza distanza 0 e a tutti gli altri nodi infinito. Ripeti n − 1 volte, per n nodi: scorri ogni arco u → v e rilassalo se u ha una distanza. Fermati prima se un'intera passata non cambia nulla. Poi fai un'altra passata. Se un arco si può ancora rilassare, dalla partenza si raggiunge un ciclo con totale negativo; altrimenti ogni distanza è la più breve, e i nodi ricordati danno i percorsi.

Un esempio

Prendi gli archi a senso unico A → B di lunghezza 4, A → C 5, B → D 2 e C → B −3, esaminati in quest'ordine, partendo da A. La passata 1 dà B 4, C 5 e D 6, poi C → B abbassa B a 5 − 3 = 2. La passata 2 abbassa D a 2 + 2 = 4. La passata 3 non cambia nulla, quindi la risposta è B 2, C 5, D 4. L'algoritmo di Dijkstra avrebbe reso definitivi B a 4 e D a 6, prima di vedere l'arco negativo. Aggiungi un arco D → C di lunghezza −4, e il ciclo C → B → D → C ha totale −5: ogni passata abbassa di nuovo le distanze, e la passata di controllo lo segnala.

Perché bastano n − 1 passate

Un percorso più breve, quando esiste, non ripete mai un nodo, quindi ha al massimo n − 1 archi. Rilassare ogni arco in una passata allunga di un arco ogni percorso più breve già noto correttamente, qualunque sia l'ordine degli archi. Così dopo la passata k sono giusti tutti i percorsi più brevi con al massimo k archi, e dopo n − 1 passate tutti. L'ordine conta comunque per la velocità: con un buon ordine può finire in una o due passate.

Storia e usi

Alfonso Shimbel descrisse il metodo nel 1955, Lester Ford Jr. nel 1956, Edward F. Moore nel 1957 e Richard Bellman nel 1958; porta il nome di due di loro, Bellman e Ford. Le sue passate possono essere eseguite da ogni router per conto suo, e per questo è diventato la base dei protocolli di routing distance vector come RIP. In finanza, prendere il logaritmo negativo dei tassi di cambio trasforma un giro redditizio di scambi di valute, un arbitraggio, in un ciclo negativo, che Bellman–Ford può trovare.

Richard Bellman nel 1962, fotografato da Alfred Eisenstaedt. Pubblicò il metodo dei cammini minimi nel 1958, dopo Shimbel, Ford e Moore.
Richard Bellman nel 1962, fotografato da Alfred Eisenstaedt. Pubblicò il metodo dei cammini minimi nel 1958, dopo Shimbel, Ford e Moore.

Provalo

Apri l'app e premi Passo. Ogni arco è a senso unico, e alcune lunghezze sono negative. Ogni passo esamina un arco, in un ordine fisso, e i riquadri mostrano la passata e quante distanze ha cambiato. Di solito presto una passata non cambia più nulla e la ricerca si ferma prima. Spunta Aggiungi un ciclo negativo e guarda le distanze scendere passata dopo passata, finché la passata di controllo trova il ciclo e lo disegna in rosso.

Domande frequenti

Qual è la complessità temporale di Bellman–Ford?

O(V · E) per V nodi ed E archi: fino a V − 1 passate, ognuna delle quali esamina ogni arco. Con l'arresto anticipato in pratica è spesso molto più veloce, e nel caso migliore basta una sola passata.

Che cos'è un ciclo negativo?

Un ciclo le cui lunghezze degli archi sommano a meno di zero. Percorrerlo più e più volte rende un percorso corto quanto si vuole, quindi le distanze più brevi verso tutti i nodi raggiungibili attraverso di esso non sono definite.

Bellman–Ford funziona sui grafi non orientati?

Solo se nessun arco è negativo: un arco negativo non orientato si può percorrere avanti e indietro, e questo è un ciclo negativo di due archi. Con archi non negativi funziona, ma l'algoritmo di Dijkstra è più veloce.

Che cos'è SPFA?

Lo Shortest Path Faster Algorithm, una versione di Bellman–Ford che, usando una coda, riesamina solo gli archi che escono dai nodi la cui distanza è appena cambiata. Spesso è molto più veloce, anche se il suo caso peggiore è lo stesso.

Pronto a provarlo?

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

Prova Bellman–Ford