LabASD - Algoritmo di Bellman-Ford

Moreno Marzolla moreno.marzolla@unibo.it

Ultimo aggiornamento: 2021-05-20

Implementare l'algoritmo di Bellman-Ford per il calcolo del cammini minimi da singola sorgente in un grafo orientato pesato senza pesi negativi. L'algoritmo richiede un nodo di partenza \(s\), e opera eseguendo dei passi di rilassamento. Dato un arco orientato \((u, v)\) di peso \(w\), e un array d[] contenente le stime delle distanze di ciascun nodo dalla sorgente, un passo di rilassamento consiste nell'operazione seguente:

if (d[u] + w < d[v]) {
    d[v] = d[u] + v;
    p[v] = u;
}

dove p[x] indica il predecessore del nodo \(x\) lungo il cammino minimo dalla sorgente a \(x\).

L'operazione di rilassamento consente di ridurre la stima \(d[v]\) della distanza del nodo \(v\) dalla sorgente nel caso in cui si scopra che attraversando l'arco \((u, v)\) si raggiunge \(v\) con una distanza inferiore.

Le distanze sono inizialmente stimate tutte \(+\infty\), ad esclusione della distanza \(d[s]\) della sorgente da se stessa che vale zero. Per rappresentare il valore \(+\infty\) si può usare il simbolo HUGE_VAL di tipo float o double definito in <math.h>. Questo simbolo è parte dello standard C90, per cui dovrebbe essere presente in tutti i compilatori compatibili (in C99 è definito un più comprensibile simbolo INFINITY). HUGE_VAL si comporta a tutti gli effetti come "infinito": è infatti strettamente maggiore di ogni valore rappresentabile dal tipo float o double, e non cambia se viene sommato ad una quantità finita.

Questo programma memorizza l'albero dei cammini minimi in due modi: come array di predecessori p[v], e in un array sp[] di lunghezza \(n\). Specificamente, sp[v] è un puntatore all'arco entrante nel nodo \(v\) lungo il cammino minimo dalla sorgente a \(v\); se \(v\) non è raggiungibile dalla sorgente, oppure se \(v\) coincide con la sorgente, si pone sp[v] = NULL.

Il programma legge il grafo da un file il cui nome è indicato sulla riga di comando, e stampa l'elenco degli archi che fanno parte dell'albero dei cammini minimi da una sorgente, oppure da una sorgente a una destinazione specificati (in questo secondo caso vengono comunque calcolati tutti i cammini minimi). Il formato dell'input è quello supportato dal tipo grafo.

Per compilare:

    gcc -std=c90 -Wall -Wpedantic graph.c bellman-ford.c -o bellman-ford

Per stampare le distanze e i cammini minimi dal nodo 0:

    ./bellman-ford graph10.in 0

Per stampare la distanza e il cammino minimo dal nodo 3 al nodo 4:

    ./bellman-ford graph10.in 3 4

Suggerimento

Nella versione base, l'algoritmo di Bellman-Ford effettua \(n-1\) fasi di rilassamento, in cui in ogni fase si esaminano tutti gli archi del grafo. Il costo è pertanto \(\Theta(nm)\).

In certi casi, si può ridurre il tempo di esecuzione con la seguente ottimizzazione: se al termine di una fase di rilassamento le distanze dei nodi non cambiano, allora l'algoritmo può terminare immediatamente. Infatti, questo significa che le distanze sono già quelle minime e risulterebbe inutile effettuare altre fasi. Questo comportamento si può realizzare con una semplice modifica alla versione base dell'algoritmo.

Con questa ottimizzazione è possibile gestire grafi più grandi, come quelli nella tabella seguente che rappresentano porzioni della rete stradale di alcuni stati americani e della città di Roma:

Dataset Nodi (\(n\)) Archi (\(m\))
Nevada 261155 618175
Maine 194505 425708
Vermont 97975 212979
Delaware 49109 119744
Roma 3353 8859

I file sono stati ottenuti dai dati forniti nel 9th DIMACS implementation challenge--Shortest Paths. Curiosamente, i grafi non sono sempre (fortemente) connessi, quindi non tutti i nodi sono raggiungibili dagli altri nodi (!!).

File