Algoritmo di Bellman-Ford

Algoritmo di Bellman-Ford
Classe	Cammino minimo
Struttura dati	Grafo
Caso peggiore temporalmente	$O(|E||V|)$

L'algoritmo di Bellman-Ford calcola i cammini minimi di un'unica sorgente su un grafo diretto pesato (dove alcuni pesi degli archi possono essere negativi). L'algoritmo di Dijkstra risolve lo stesso problema in un tempo computazionalmente inferiore, ma richiede che i pesi degli archi siano non-negativi. Per questo, Bellman-Ford è usato di solito quando sul grafo sono presenti pesi degli archi negativi.

Secondo Robert Sedgewick «i pesi negativi non sono solamente una curiosità matematica; […] si presentano in modo naturale quando riduciamo altri problemi a quelli di cammini minimi» e forniscono un esempio specifico di una riduzione dal problema NP-completo del cammino hamiltoniano. Se un grafo contiene un ciclo di peso totale negativo allora sono ottenibili pesi arbitrariamente piccoli e quindi non c'è soluzione; Bellman-Ford individua questo caso.

Descrizione

Un esempio di algoritmo Bellman-Ford utilizzato su un grafico 5-vetrex

L'algoritmo di Bellman-Ford è nella sua struttura base molto simile a quello di Dijkstra, ma invece di selezionare il nodo di peso minimo, tra quelli non ancora processati, con tecnica greedy, semplicemente processa tutti gli archi e lo fa $\left|V\right|-1$ volte, dove $\left|V\right|$ è il numero di vertici nel grafo. Le ripetizioni permettono alle distanze minime di propagarsi accuratamente attraverso il grafo, poiché, in assenza di cicli negativi il cammino minimo può solo visitare ciascun nodo al più una volta. Diversamente da quello con tecnica greedy, il quale dipende da certe assunzioni strutturali derivate dai pesi positivi, questo semplice approccio si applica al caso più generale.

L'algoritmo di Bellman-Ford ha una complessità temporale $O(\left|V\right|\left|E\right|)$, dove $\left|V\right|$ ed $\left|E\right|$ sono rispettivamente il numero di vertici e di archi del grafo.

procedure BellmanFord(list vertici, list archi, vertice source)
  // Questa implementazione prende in ingresso un grafo, rappresentato come
  // liste di vertici ed archi, e modifica i vertici in modo tale che i loro
  // attributi distanza e predecessore memorizzino i cammini minimi.

     // Passo 1: Inizializza il grafo
     for each vertice v in vertici:
        if v is source then v.distance := 0      //la funzione distance ritorna la distanza dal nodo iniziale s
        else v.distance := infinity
        v.predecessor := null

     // Passo 2: Processa gli archi ripetutamente
     for i from 1 to size(vertici)-1:
        for each arco uv in archi:
           u := uv.source
           v := uv.destination             // uv è l'arco da u a v
           if v.distance > u.distance + uv.weight:
              v.distance := u.distance + uv.weight
              v.predecessor := u

     // Passo 3: controlla la presenza di cicli negativi
     for each arco uv in archi:
        u := uv.source
        v := uv.destination
        if v.distance > u.distance + uv.weight:
           error "Il grafo contiene un ciclo di peso negativo"

Applicazione negli algoritmi di instradamento

Una variante dell'algoritmo di Bellman-Ford è usata nei protocolli di routing distance vector, ad esempio il RIP (Routing Information Protocol), un algoritmo distribuito che coinvolge un numero di nodi (routers) all'interno di un sistema autonomo (AS).

In questo grafico di esempio, supponendo che A sia la sorgente e gli archi vengano elaborati nell'ordine peggiore, da destra a sinistra, è necessario l'intero | V |−1 o 4 iterazioni per far convergere le stime della distanza. Viceversa, se gli archi vengono elaborati nell'ordine migliore, da sinistra a destra, l'algoritmo converge in un'unica iterazione.

Funzionamento

Si parte dal dare al nodo sorgente valore 0 e valore infinito a tutti gli altri.

L'idea è quella di partire dal nodo sorgente e cominciare a guardare i nodi adiacenti, cioè che distano un passo solo. Si assegna loro il valore del costo per raggiungerli (determinato dal costo dell'arco + il valore del nodo da cui si è partiti, che in questo caso è 0 visto che stiamo partendo dalla sorgente). A questo punto per ciascuno dei nodi raggiunti si procede allo stesso modo: si vedono i nodi che gli distano uno e si assegna loro il valore dell'arco percorso per raggiungerli più quello già assegnato al nodo da cui si è partiti (assegno loro il nuovo valore solo se è più piccolo di quello che già avevano: la prima volta che li raggiungi è certamente più piccolo in quanto abbiamo detto che inizialmente diamo a tutti i nodi valore infinito). Ad ogni passaggio i nodi raggiunti lo step precedente (considera nodi raggiunti solo quelli a cui hai aggiornato il valore) diventano punto di partenza per raggiungere i nodi adiacenti, il cui valore diventa (se è minore di quello che già possiedono) quello dell'arco percorso per raggiungerli + il valore del nodo da cui li si è raggiunti (e in tal caso diventano a loro volta nuovi punti di partenza). Se il grafo ha N nodi è certo che dopo N-1 giri tutti i nodi hanno a loro assegnato il costo minimo per essere raggiunti dal nodo sorgente. Ovviamente ad ogni giro quando aggiorni il valore di un nodo devi salvarti il percorso associato per raggiungerlo dalla sorgente, così quando avrai finito le iterazioni oltre ad avere tutti i costi minimi avrai anche i percorsi associati cioè i percorsi a costo minimo per raggiungere ogni nodo del grafo dal nodo sorgente.

Principali svantaggi dell'algoritmo di Bellman-Ford

• Modesta scalabilità della rete.
• Convergenza lenta: i cambiamenti nella topologia della rete non si riflettono velocemente nella composizione delle tabelle, poiché gli aggiornamenti sono fatti nodo dopo nodo.
• Conto all'infinito: se si interrompe il collegamento con un nodo, gli altri nodi possono impiegare un tempo infinito per aumentare gradatamente la stima della distanza per quel nodo a meno di non adoperare uno scalare come soglia, oltre il quale, il nodo viene considerato non raggiungibile e quindi fuori dalla rete.

Voci correlate

• Si vedano gli articoli nella categoria Protocolli di routing
• Si vedano gli articoli nel progetto di Matematica Teoria dei Grafi
• Algoritmo di Dijkstra
• Distance vector

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sull'algoritmo di Bellman–Ford