L’algoritmo di Bellman–Ford risolve il seguente problema: dato un grafo orientato D =(V,A) con costi (ce)e∈A sugli archi, dove D non contiene alcun ciclo di costo negativo, e dato un nodo sorgente s ∈ V , trovare, per ogni v ∈ V , un cammino di costo minimo da s a v (o stabilire che non c’`e alcun cammino da s a v).
Da ora in avanti, dato un arco (u,v) ∈ A, indicheremo il suo costo con cuv invece di usare la notazione pi`u pesante c(u,v).
Sia n =∣V ∣. Dato un cammino orientato P da s ad un nodo v ∈ V e dato k ∈ {0,... ,n −1}, diciamo che P `e un cammino k-ristretto se ha al massimo k archi. Per ogni v ∈ V , indichiamo con ℓk(v) il costo di un cammino k-ristretto da s a v di costo minimo, dove ℓk(v) = +∞ se non esiste alcun cammino k-ristretto da s a v.
Proposizione 6.5 Sia D = (V,A) un grafo orientato, siano s,v ∈ V e siano (ce)e∈A costi tali che D non contenga alcun ciclo di costo negativo. Sia P un cammino k-ristretto di costo
6.2. L’ALGORITMO DI BELLMAN–FORD 67
Figura 6.1: Esempio di applicazione dell’algoritmo per il calcolo dei cammini di lunghezza minima dal nodo s. La prima figura rappresenta l’inizializzazione (passo 1), mentre ciacuna delle figure successive corrisponde ad un’iterazione del ciclo 2. In ciascuna di queste: i numeri accanto ai nodi rappresentano le distanze d(v) calcolate dall’algoritmo; i nodi in R sono precisamente quelli con un’etichetta diversa da +∞; gli archi in grassetto vanno da p(v) a v per ogni v ∈ R ∖{s}. Si noti che all’ultima iterazione la scelta dell’arco da aggiungere non `e univoca: avremmo potuto scegliere l’arco verticale pi`u a destra. Si osservi anche che dopo la terza iterazione `e possibile arrestare l’esecuzione dell’algoritmo, in quanto R = V . Al termine dell’algoritmo, gli archi in grassetto costituiscono un albero di cammini di lunghezza minima.
minimo da s a v, per qualche k ∈{1,... ,n − 1}. Se u `e il predecessore di v in P, allora Psu `e un cammino (k − 1)-ristretto di costo minimo da s e u.
Dimostrazione. Supponiamo per assurdo che esista un cammino (k − 1)-ristretto Q da s a u tale che c(Q) < c(Psu). Se Q non contiene v, allora la sequenza Q,(u,v),v definisce un cammino k-ristretto da s a v il cui costo `e c(Q) + cuv<c(Psu) + cuv=c(P), in contraddizione con il fatto che P `e un cammino k-ristretto di costo minimo da s a v. Supponiamo dunque che Qcontenga v. Allora la sequenza Qvu,(u,v),v definisce un ciclo C. Poich´e P `e un cammino k-ristretto di costo minimo da s a v e Qsv ha meno di k archi, c(P) ≤ c(Qsv). Dunque
c(C) = c(Qvu) + cuv=(c(Q) − c(Qsv)) + (c(P) − c(Psu))
=(c(Q) − c(Psu)) + (c(P) − c(Qsv)) < 0 + 0.
Pertanto C `e un ciclo di costo negativo, contro le ipotesi. ◻ La proposizione precedente implica che se D non contiene cicli di costo negativo, allora, per ogni v ∈ V e k ∈{1,... ,n − 1},
ℓk(v) = min
u∶(u,v)∈A{ℓk−1(u) + cuv}. (6.2)
Osserviamo inoltre che vale l’ovvia propriet`a ℓk(v) ≤ ℓk−1(v).
Il seguente risultato rispecchia in qualche modo il Lemma 6.2 per il caso dei cammini di lunghezza minima.
Lemma 6.6 Sia D =(V,A) un grafo orientato, siano s,v ∈ V e siano (ce)e∈Acosti tali che D non contenga alcun ciclo di costo negativo. Fissato k ∈{1,... ,n−1}, supponiamo che ℓk(v) <
ℓk−1(v). Sia u un nodo che realizza il minimo in (6.2), cio`e (u,v) ∈ A e ℓk(v) = ℓk−1(u)+cuv. Allora, se Q `e un qualunque cammino (k − 1)-ristretto di costo minimo da s a u, la sequenza Q,(u,v),v costituisce un cammino k-ristretto di costo minimo da s a v.
Dimostrazione. Se Q non contiene v, allora la sequenza Q,(u,v),v costituisce un cammino k-ristretto da s a v il cui costo `e c(Q) + cuv = ℓk−1(u) + cuv =ℓk(v), quindi `e un cammino k-ristretto di costo minimo da s a v. Basta dunque dimostrare che Q effettivamente non contiene v. Se Q contenesse v, allora la sequenza Qvu,(u,v),v definirebbe un ciclo C, il cui costo sarebbe
c(C) = c(Qvu) + cuv=(c(Q) − c(Qsv)) + (ℓk(v) − ℓk−1(u))
=(c(Q) − ℓk−1(u)) + (ℓk(v) − c(Qsv)) < 0 + (ℓk−1(v) − c(Qsv)) ≤ 0,
una contraddizione. ◻
Si tenga presente che il risultato del lemma precedente potrebbe non valere se ℓk(v) = ℓk−1(v). (Tuttavia, si vede subito dalla dimostrazione che se D non contenesse n´e cicli di costo negativo n´e cicli di costo nullo allora il risultato varrebbe anche quando ℓk(v) = ℓk−1(v).)
Diamo ora una descrizione formale dell’algoritmo di Bellman–Ford. Come nel caso dell’al-goritmo per cammini di lunghezza minima visto in precedenza, manterremo un predecessore p(v) di ogni nodo v ∈ V ∖ {s}, dove p(v) sar`a il nodo che precede v in un cammino di costo minimo da s a v. Grazie al Lemma 6.6, tramite i p(v) sar`a possibile ricostruire tutti i cammini minimi con sorgente s.
Algoritmo di Bellman–Ford
Input: Un grafo orientato D =(V,A), un nodo s ∈ V e costi (ce)e∈A tali che D non contenga cicli di costo negativo.
Output: Per ogni v ∈ V , il costo ℓ(v) di un cammino minimo da s a v ed un nodo p(v) che precede v in un tale cammino (se ℓ(v) < +∞; altrimenti p(v) non `e definito).
1. Si ponga ℓ0(s) ∶= 0 e ℓ0(v) ∶= +∞ per ogni v ∈ V ∖ {s};
2. Per k = 1, . . . ,∣V ∣ − 1:
2.1 Si ponga ℓk(v) ∶= ℓk−1(v) per ogni v ∈ V ; 2.2 Per ogni(u,v) ∈ A:
Se ℓk(v) > ℓk−1(u) + cuv,
si aggiornino ℓk(v) ∶= ℓk−1(u) + cuv e p(v) ∶= u;
3. Si ponga ℓ(v) ∶= ℓ∣V ∣−1(v) per ogni v ∈ V .
6.2. L’ALGORITMO DI BELLMAN–FORD 69 Teorema 6.7 L’algoritmo di Bellman–Ford funziona correttamente ed esegue O(∣V ∣ ⋅ ∣A∣) operazioni.
Dimostrazione. Per dimostrare la correttezza dell’algoritmo, `e sufficiente osservare che, alla fine della k-esima iterazione, ℓk(v) `e esattamente il costo minimo di un cammino k-ristretto da s a v. Questo pu`o essere facilmente dimostrato per induzione, osservando che la propriet`a
`e chiaramente vera per ℓ0 dopo l’esecuzione del passo 1 e che si mantiene vera grazie alla formula (6.2). Poich´e ogni cammino in D ha al massimo∣V ∣ − 1 archi, l’istruzione 3 definisce ℓ(v) come il costo minimo tra tutti i cammini da s a v.
Per verificare che i puntatori p(v) permettono di ricostruire a ritroso i cammini minimi, osserviamo che se ℓk(v) = ℓk−1(v), allora la k-esima iterazione dell’algoritmo non aggiorna il predecessore p(v) (e questa scelta `e corretta, perch´e il cammino (k − 1)-ristretto di costo minimo gi`a trovato `e anche un cammino k-ristretto di costo minimo); in caso contrario, detto uun nodo che realizza il minimo in (6.2), l’algoritmo pone p(v) = u. Il Lemma 6.6 garantisce che questa scelta `e corretta.
Per quanto riguarda la complessit`a, l’algoritmo compie ∣V ∣ − 1 iterazioni, una per ogni valore di k. Ad ogni iterazione, vengono considerati uno alla volta tutti gli archi e, per ciascuno di essi, viene eseguito un confronto ed eventualmente un aggiornamento di ℓk(v) e p(v). Nel complesso, vengono svolte O(∣V ∣ ⋅ ∣A∣) operazioni. ◻ Sia R l’insieme dei nodi raggiungibili da s. Al termine dell’esecuzione dell’algoritmo di Bellman–Ford, ℓ(v) < +∞ esattamente per i nodi v ∈ R; inoltre, per tali nodi p(v) `e definito.
Come nel caso del problema dei cammini di lunghezza minima, il sottografo T =(R,A′), dove A′={(p(v),v) ∶ v ∈ R∖{s}}, `e un’arborescenza con radice s. Per ogni v ∈ R, l’unico cammino da s a v in T `e un cammino di costo minimo da s a v in D. Si dice che T `e un albero di cammini di costo minimo.
Esempio 6.8 Risolvere il problema dei cammini minimi a partire dal nodo s nel grafo in figura (i numeri vicino agli archi ne indicano il costo).
s
Il grafo assegnato non contiene alcun ciclo di costo negativo: per il momento dobbiamo accontentarci di una verifica “a occhio”, ma vedremo nella Sezione 6.4 come controllare que-sta propriet`a in modo efficiente. Possiamo dunque applicare l’algoritmo di Bellman–Ford.
Rappresentiamo le iterazioni dell’algoritmo attraverso una tabella, con una riga per ogni ite-razione e una colonna per ogni nodo. Nella posizione situata nella riga relativa all’iteite-razione k e nella colonna relativa al nodo v, scriviamo il valore di ℓk(v) ed il nodo p(v) ottenuti alla fine della k-esima iterazione. La riga k = 0 corrisponde all’inizializzazione (passo 1 dell’algoritmo).
Poich´e il grafo ha sei nodi, l’algoritmo eseguir`a cinque iterazioni.
Iterazione s a b c d e
Come si evince dalla dimostrazione del Teorema 6.7, alla fine della k-esima iterazione la tabella fornisce i cammini minimi k-ristretti. Si noti che dopo l’iterazione k = 4 non viene fatto alcun aggiornamento. Questo vuol dire che tutti i cammini di costo minimo trovati hanno lunghezza inferiore o uguale a 4. L’ultima riga della tabella permette di costruire un albero di cammini di costo minimo, come rappresentato in figura.
s
In questa sezione mostriamo come la programmazione lineare possa essere utilizzata per risolvere il problema di trovare il cammino di costo minimo tra due nodi fissati.
Sar`a utile il seguente risultato. Ricordiamo che indichiamo con ℓ(v) il costo di un cammino minimo da s a v.
Proposizione 6.9 Sia D =(V,A) un grafo orientato con costi (ce)e∈A tali che D non con-tenga alcun ciclo orientato di costo negativo. Fissiamo s ∈ V tale che ogni nodo v ∈ V sia raggiungibile da s. Allora valgono le condizioni di Bellman:
ℓ(v) − ℓ(u) ≤ cuv per ogni (u,v) ∈ A. (6.3) Dimostrazione. Supponiamo per assurdo che esista un arco(u,v) ∈ A tale che ℓ(v)−ℓ(u) > cuv. Sia P un cammino di costo minimo da s a u. Se v ∉ V(P), allora la sequenza P,(u,v),v forma un cammino da s a v di costo ℓ(u) + cuv<ℓ(v), una contraddizione. Dunque possiamo assumere che v sia un nodo di P . Si noti che il sottocammino Psv ha costo almeno ℓ(v).
Allora la sequenza Pvu,(u,v),v definisce un ciclo C in D per cui vale c(C) = c(P) − c(Psv) + cuv≤ℓ(u) − ℓ(v) + cuv<0,
una contraddizione. ◻
Fissiamo un grafo orientato D = (V,A) con costi (ce)e∈A sugli archi e due nodi s, t ∈ V . Definiamo una variabile xe per ogni arco e ∈ A. Ad ogni cammino P da s a t associamo il vettore x ∈ RA cos`ı definito:
xe=⎧⎪⎪
⎨⎪⎪⎩
1 se e ∈ A(P)
0 altrimenti. (6.4)