Algoritmo di Bellman-Ford

Da Wikipedia, l'enciclopedia libera.

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 fornisce 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.

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 |V|-1 volte, dove |V| è 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(|V||E|), dove |V| ed |E| sono rispettivamente il numero di vertici e di archi del grafo.

  procedure BellmanFord(list vertices, list edges, vertex 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 vertex v in vertices:
        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(vertices)-1:       
        for each edge uv in edges:
           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 edge uv in edges:
        u := uv.source
        v := uv.destination
        if v.distance > u.distance + uv.weight:
           error "Il grafo contiene un ciclo di peso negativo"