Algoritmo di Bellman-Ford

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)^[1]. 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^[2][3].

Algoritmo di Bellman-Ford
Classe	Cammino minimo
Struttura dati	Grafo
Caso peggiore temporalmente	${\displaystyle O(|E||V|)}$
Caso peggiore spazialmente	${\displaystyle O(|V|)}$
Ottimale	Sì

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^[4]. 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^[5][6].

Storia

L'algoritmo fu proposto per la prima volta da Alfonso Shimbel nel 1955, ma prende il nome da Richard Bellman e Lester Ford Jr. che lo pubblicarono rispettivamente nel 1958 e nel 1956^[7][8]. Anche Edward F. Moore pubblicò una variante dell'algoritmo nel 1959 e per questo motivo viene talvolta chiamato anche algoritmo di Bellman-Ford-Moore^[9].

L'algoritmo rappresenta un'implementazione del principio di ottimalità di Bellman applicato ai problemi di cammino minimo, dimostrando come la programmazione dinamica possa essere utilizzata efficacemente anche in presenza di pesi negativi.

Descrizione

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

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 ${\displaystyle \left|V\right|-1}$ volte, dove ${\displaystyle \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^[10].

Principio di funzionamento

L'algoritmo si basa sul principio di rilassamento degli archi: per ogni arco (u,v) con peso w, se la distanza da sorgente a u più w è minore della distanza corrente da sorgente a v, allora aggiorna la distanza di v. Questo processo viene ripetuto |V|-1 volte per garantire che tutti i cammini minimi vengano trovati^[11].

Invariante dell'algoritmo: Dopo k iterazioni, l'algoritmo ha trovato tutti i cammini minimi che utilizzano al massimo k archi.

Analisi di complessità

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

Analisi dettagliata

• Inizializzazione: O(V) per impostare le distanze
• Rilassamento archi: O(E) per ogni iterazione, ripetuto V-1 volte = O(VE)
• Controllo cicli negativi: O(E) per verificare se esistono miglioramenti possibili
• Totale: O(V + VE + E) = O(VE)

Complessità spaziale: O(V) per memorizzare le distanze e i predecessori.

Confronto con altri algoritmi

Algoritmo	Complessità temporale	Pesi negativi	Cicli negativi
Bellman-Ford	O(VE)	✓	Rileva
Dijkstra	O((V+E) log V)	✗	N/A
Floyd-Warshall	O(V³)	✓	Rileva
SPFA	O(VE) medio, O(VE) pessimo	✓	Rileva

Implementazione

Algoritmo principale

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:
        //la funzione distance ritorna la distanza dal nodo iniziale s
        if v is source then v.distance := 0
        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"

Implementazione ottimizzata

È possibile migliorare l'efficienza pratica dell'algoritmo terminando anticipatamente se nessun rilassamento viene effettuato in un'iterazione:

procedure BellmanFordOptimized(grafo G, vertice source):
    // Inizializzazione
    for each vertice v in G.V:
        v.distance = infinity
        v.predecessor = null
    source.distance = 0
    
    // Rilassamento con terminazione anticipata
    for i = 1 to |G.V| - 1:
        hasChanged = false
        for each arco (u,v) in G.E:
            if u.distance != infinity and u.distance + weight(u,v) < v.distance:
                v.distance = u.distance + weight(u,v)
                v.predecessor = u
                hasChanged = true
        
        if not hasChanged:
            break  // Terminazione anticipata
    
    // Controllo cicli negativi
    for each arco (u,v) in G.E:
        if u.distance != infinity and u.distance + weight(u,v) < v.distance:
            return "Ciclo negativo rilevato"
    
    return "Successo"

Ricostruzione del cammino

procedure PrintPath(vertice target):
    if target.predecessor is null:
        print target.name
    else:
        PrintPath(target.predecessor)
        print " -> " + target.name

procedure GetPath(vertice target):
    path = []
    current = target
    while current is not null:
        path.prepend(current)
        current = current.predecessor
    return path

Esempio passo-passo

Consideriamo un grafo con vertici {A, B, C, D} e archi:

• A→B (peso: 4)
• A→C (peso: 2)
• B→C (peso: -3)
• C→D (peso: 4)
• B→D (peso: 3)

Con sorgente A:

Inizializzazione:

• A: distanza = 0, predecessore = null
• B: distanza = ∞, predecessore = null
• C: distanza = ∞, predecessore = null
• D: distanza = ∞, predecessore = null

Iterazione 1:

• Rilassamento A→B: B.distanza = min(∞, 0+4) = 4, predecessore = A
• Rilassamento A→C: C.distanza = min(∞, 0+2) = 2, predecessore = A
• Altri archi non migliorano le distanze

Iterazione 2:

• Rilassamento B→C: C.distanza = min(2, 4+(-3)) = 1, predecessore = B
• Rilassamento C→D: D.distanza = min(∞, 1+4) = 5, predecessore = C
• Rilassamento B→D: D.distanza = min(5, 4+3) = 5, nessun cambiamento

Iterazione 3:

• Nessun miglioramento possibile, algoritmo termina

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)^[13].

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 distribuito

Nel contesto dei protocolli di routing, ogni router: 1. Mantiene una tabella delle distanze verso tutte le destinazioni 2. Periodicamente scambia informazioni con i router vicini 3. Aggiorna le sue tabelle usando il principio di Bellman-Ford 4. Propaga i cambiamenti ai router adiacenti

Funzionamento

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

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^[10][14].

Rilevamento di cicli negativi

Una delle caratteristiche distintive dell'algoritmo di Bellman-Ford è la sua capacità di rilevare cicli negativi^[15].

Principio teorico

Se un grafo non contiene cicli negativi raggiungibili dalla sorgente, allora tutti i cammini minimi contengono al massimo |V|-1 archi. Se dopo |V|-1 iterazioni è ancora possibile rilassare qualche arco, significa che esiste un ciclo negativo.

Localizzazione del ciclo negativo

procedure FindNegativeCycle(grafo G):
    // Esegui Bellman-Ford fino alla rilevazione
    if BellmanFord(G, source) == "Ciclo negativo rilevato":
        // Trova i nodi del ciclo
        for each vertice v in G.V:
            v.inCycle = false
        
        // Marca i nodi raggiungibili da archi rilassabili
        for each arco (u,v) in G.E:
            if u.distance + weight(u,v) < v.distance:
                v.inCycle = true
        
        // Propaga la marca attraverso i predecessori
        changed = true
        while changed:
            changed = false
            for each vertice v in G.V:
                if v.inCycle and v.predecessor != null and not v.predecessor.inCycle:
                    v.predecessor.inCycle = true
                    changed = true
        
        return {v | v.inCycle}

Varianti e ottimizzazioni

Algoritmo SPFA

L'algoritmo Shortest Path Faster Algorithm (SPFA) è una variante ottimizzata che utilizza una coda per processare solo i vertici che potrebbero portare a miglioramenti^[16]:

procedure SPFA(grafo G, vertice source):
    for each vertice v in G.V:
        v.distance = infinity
        v.inQueue = false
    source.distance = 0
    
    queue Q = {source}
    source.inQueue = true
    
    while Q is not empty:
        u = Q.dequeue()
        u.inQueue = false
        
        for each arco (u,v) in G.E:
            if u.distance + weight(u,v) < v.distance:
                v.distance = u.distance + weight(u,v)
                v.predecessor = u
                if not v.inQueue:
                    Q.enqueue(v)
                    v.inQueue = true

Ottimizzazione per grafi sparsi

Per grafi con pochi archi (|E| << |V|²), l'implementazione può essere ottimizzata usando liste di adiacenza e saltando i vertici irraggiungibili.

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^[17].

Applicazioni pratiche

Routing in reti

• RIP (Routing Information Protocol)
• BGP (Border Gateway Protocol) in forma modificata
• Protocolli di routing per reti mesh wireless

Ottimizzazione finanziaria

• Rilevamento di arbitraggi nei mercati valutari
• Analisi di opportunità di profitto in trading

Teoria dei giochi

• Calcolo di equilibri in giochi a somma zero
• Ottimizzazione di strategie competitive