Vai al contenuto

3.5 L'algoritmo di Bellman–Ford

Definizione 3.16: etichette con al più \(k\) archi

Per \(k \ge 0\) e \(j \in N\), \(d^k(j)\) è la lunghezza minima di una passeggiata da \(s\) a \(j\) con al più \(k\) archi, e \(d^k(j)=+\infty\) se non ce n'è nessuna.

Lemma 3.17: ricorsione delle etichette

\(d^0(s)=0\), \(d^0(j)=+\infty\) per \(j \neq s\), e per ogni \(k \ge 1\)

\[ d^k(j)=\min\Big\{\, d^{k-1}(j),\; \min_{(i,j) \in \delta^-(j)} \big( d^{k-1}(i)+d_{ij} \big) \Big\}, \qquad \forall j \in N . \]
Dimostrazione

L'unica passeggiata con \(0\) archi è la passeggiata \(s\). Per \(k \ge 1\), una passeggiata verso \(j\) con al più \(k\) archi ha al più \(k-1\) archi, con lunghezza minima \(d^{k-1}(j)\), oppure ha esattamente \(k\) archi e ultimo arco \((i,j)\): è una passeggiata verso \(i\) con \(k-1\) archi seguita da \((i,j)\), e la sua lunghezza minima è \(\min_{(i,j)}\big(d^{k-1}(i)+d_{ij}\big)\). □

Algoritmo: Algoritmo di Bellman–Ford

Input: un grafo orientato \(G=(N,A)\) con lunghezze \(d_{ij}\) di qualsiasi segno, una sorgente \(s \in N\)
Output: le distanze \(\tilde{d}(j)\) e i predecessori, oppure un ciclo negativo raggiungibile da \(s\)
1Passo 0 (inizializzazione). Porre \(d^0(s):=0\), \(d^0(j):=+\infty\) per \(j \neq s\), e \(k:=1\).
2Passo 1 (passata \(k\)). Calcolare \(d^k(j)\) per ogni \(j \in N\) con la ricorsione del Lemma 3.17;
3 se \(d^k(j)<d^{k-1}(j)\), porre \(\mathit{pred}(j)\) uguale alla coda \(i\) dell'arco che realizza il minimo.
4Passo 2 (test). Se \(d^k=d^{k-1}\), STOP: \(\tilde{d}=d^k\).
5 Se \(k=n\), STOP: un ciclo negativo è raggiungibile da \(s\). Altrimenti porre \(k:=k+1\) e andare al Passo 1.

  • Ogni passata dipende solo dalle etichette della passata precedente: se \(d^k=d^{k-1}\), tutte le passate successive ripetono le stesse etichette, e l'algoritmo può fermarsi.

  • Negli esempi, i pareggi nel minimo si risolvono con la coda \(i\) di indice minimo, e il predecessore cambia solo quando l'etichetta diminuisce strettamente.

Teorema 3.18: correttezza di Bellman–Ford

Se nessun ciclo negativo è raggiungibile da \(s\), allora \(d^{n-1}(j)=\tilde{d}(j)\) per ogni \(j \in N\), e l'algoritmo si ferma a una passata \(k \le n\) con \(d^k=d^{k-1}=\tilde{d}\).

Dimostrazione

Un cammino ha al più \(n-1\) archi, quindi \(d^{n-1}(j) \le \tilde{d}(j)\). Per il Lemma 3.3 (che richiede solo i cicli raggiungibili da \(s\)) ogni passeggiata da \(s\) a \(j\) contiene un cammino non più lungo, quindi \(d^k(j) \ge \tilde{d}(j)\) per ogni \(k\).

  • Quindi \(d^{n-1}=d^{n}=\tilde{d}\).

  • Le etichette non aumentano mai, e l'algoritmo si ferma alla prima passata \(k\) con \(d^k=d^{k-1}\), che è al più \(n\); da quella passata in poi le etichette non cambiano più, quindi \(d^k=d^{n-1}=\tilde{d}\).

□

Teorema 3.19: rilevamento di un ciclo negativo

Un ciclo negativo è raggiungibile da \(s\) se e solo se \(d^n \neq d^{n-1}\). In tal caso, sia \(d^n(j)<d^{n-1}(j)\); leggendo i predecessori all'indietro a partire da \(j\), una riga per passata, partendo dalla riga \(n\) della tabella, si ottiene una passeggiata da \(s\) a \(j\) con \(n\) archi che contiene un ciclo negativo.

Dimostrazione

Se nessun ciclo negativo è raggiungibile da \(s\), allora \(d^n=d^{n-1}\) per il Teorema 3.18. Viceversa, sia \(d^n(j)<d^{n-1}(j)\).

  1. Ogni passeggiata verso \(j\) di lunghezza \(d^n(j)\) con al più \(n\) archi ha esattamente \(n\) archi, altrimenti \(d^{n-1}(j) \le d^n(j)\).

  2. Sia \(i\) il predecessore di \(j\) nella riga \(n\), quindi \(d^n(j)=d^{n-1}(i)+d_{ij}\). Una passeggiata che realizza \(d^{n-1}(i)\) seguita da \((i,j)\) realizza \(d^n(j)\), quindi ha esattamente \(n-1\) archi: \(d^{n-1}(i)<d^{n-2}(i)\), e \(i\) ha un predecessore nella riga \(n-1\).

  3. Ripetendo il ragionamento fino alla riga \(1\), il cui predecessore è \(s\), si ottiene una passeggiata \(W\) da \(s\) a \(j\) con \(n\) archi e \(d(W)=d^n(j)\).

  4. \(W\) ha \(n+1\) nodi, quindi ripete un nodo e contiene un ciclo \(C\). Togliendo \(C\) si ottiene una passeggiata verso \(j\) con meno di \(n\) archi, di lunghezza \(d(W)-d(C) \ge d^{n-1}(j)>d^n(j)=d(W)\). Quindi \(d(C)<0\), e \(C\) è raggiungibile da \(s\) lungo \(W\). □

Proposizione 3.20: l'albero dei predecessori di Bellman–Ford

Se nessun ciclo negativo è raggiungibile da \(s\), all'arresto gli archi \((\mathit{pred}(j),j)\), per i nodi \(j \neq s\) con etichetta finita, formano un albero dei cammini minimi dei nodi raggiungibili.

Dimostrazione

Siano \(d=\tilde{d}\) le etichette finali, e sia \(t(j)\) l'ultima passata in cui l'etichetta di \(j\) è diminuita; \(t(s)=0\), perché \(d^k(s)=0\) per ogni \(k\). Sia \(p=\mathit{pred}(j)\).

  1. Nella passata \(t(j)\), \(d(j)=d^{t(j)-1}(p)+d_{pj} \ge d(p)+d_{pj}\), perché le etichette non aumentano mai.

  2. Per il Teorema 3.5, \(d(j) \le d(p)+d_{pj}\). Quindi \(d(j)=d(p)+d_{pj}\) e \(d(p)=d^{t(j)-1}(p)\): l'etichetta di \(p\) non è cambiata dopo la passata \(t(j)-1\), quindi \(t(p)<t(j)\).

  3. Passando al predecessore, \(t\) diminuisce strettamente, quindi la sequenza termina in \(s\), lungo archi stretti: il cammino dell'albero da \(s\) a \(j\) ha lunghezza \(d(j)\). □

Teorema 3.21: tempo di esecuzione di Bellman–Ford

L'algoritmo di Bellman–Ford richiede tempo \(O(n\,m)\).

Dimostrazione

Una passata calcola \(d^k(j)\) per ogni \(j\) esaminando la stella entrante \(\delta^-(j)\), quindi esamina ogni arco una volta: tempo \(O(n+m)\). Le passate sono al più \(n\), e il totale è \(O(n(n+m))\), cioè \(O(n\,m)\) quando \(m \ge n-1\), come sotto (A1). □

3.5.1 Bellman–Ford sul grafo di riferimento

Esempio 3.7: Bellman–Ford con un arco negativo

Usiamo le lunghezze \(d'\) dell'Esempio 3.1 con \(d'_{54}=-3\) al posto di \(2\). I due cicli hanno lunghezze \(7\) e \(8-3+1=6\), quindi non c'è alcun ciclo negativo. Ogni riga è una passata \(k\); accanto a un'etichetta che è diminuita, tra parentesi il nuovo predecessore:

\[ \begin{array}{c|cccccc} \hline {k} & {d^k(1)} & {d^k(2)} & {d^k(3)} & {d^k(4)} & {d^k(5)} & {d^k(6)} \\ \hline {0} & {0} & {\infty} & {\infty} & {\infty} & {\infty} & {\infty} \\ {1} & {0} & {7} ({1}) & {2} ({1}) & {\infty} & {\infty} & {\infty} \\ {2} & {0} & {5} ({3}) & {2} & {10} ({2}) & {10} ({3}) & {\infty} \\ {3} & {0} & {5} & {2} & {7} ({5}) & {10} & {15} ({4}) \\ {4} & {0} & {5} & {2} & {7} & {10} & {12} ({4}) \\ {5} & {0} & {5} & {2} & {7} & {10} & {12} \\ \hline \end{array} \]
  • Nella passata \(3\), \(d^3(4)=\min\{10,\; d^2(2)+3,\; d^2(5)-3\}=\min\{10,8,7\}=7\), con predecessore \(5\).

  • La passata \(5\) ripete le etichette della passata \(4\): l'algoritmo si ferma con \(\tilde{d}=(0,5,2,7,10,12)\), dopo \(5\) passate invece delle \(n=6\) consentite.

  • L'albero dei cammini minimi ha gli archi \((1,3)\), \((3,2)\), \((3,5)\), \((5,4)\), \((4,6)\), e il cammino minimo verso \(6\) è \(1,3,5,4,6\), di lunghezza \(2+8-3+5=12\).

Figura 4

Esempio 3.8: Bellman–Ford rileva un ciclo negativo

Con le lunghezze \(d''\) dell'Esempio 3.2 (\(d''_{54}=-10\)) l'algoritmo esegue tutte le \(n=6\) passate:

\[ \begin{array}{c|cccccc} \hline {k} & {d^k(1)} & {d^k(2)} & {d^k(3)} & {d^k(4)} & {d^k(5)} & {d^k(6)} \\ \hline {0} & {0} & {\infty} & {\infty} & {\infty} & {\infty} & {\infty} \\ {1} & {0} & {7} ({1}) & {\mathbf{2}} ({\mathbf{1}}) & {\infty} & {\infty} & {\infty} \\ {2} & {0} & {5} ({3}) & {2} & {10} ({2}) & {\mathbf{10}} ({\mathbf{3}}) & {\infty} \\ {3} & {0} & {5} & {2} & {\mathbf{0}} ({\mathbf{5}}) & {10} & {15} ({4}) \\ {4} & {0} & {5} & {\mathbf{1}} ({\mathbf{4}}) & {0} & {10} & {5} ({4}) \\ {5} & {0} & {4} ({3}) & {1} & {0} & {\mathbf{9}} ({\mathbf{3}}) & {5} \\ {6} & {0} & {4} & {1} & {\mathbf{-1}} ({\mathbf{5}}) & {9} & {5} \\ \hline \end{array} \]
  • Nella passata \(6\) l'etichetta del nodo \(4\) scende da \(0\) a \(-1\): \(d^6 \neq d^5\), e un ciclo negativo è raggiungibile da \(1\).

  • Leggendo all'indietro a partire dal nodo \(4\) (valori in grassetto): la riga \(6\) dà \(\mathit{pred}=5\), la riga \(5\) per il nodo \(5\) dà \(3\), la riga \(4\) per il nodo \(3\) dà \(4\), poi \(5\), \(3\), \(1\). La passeggiata è

    \[ 1,\;3,\;5,\;4,\;3,\;5,\;4, \qquad\text{di lunghezza } 2+8-10+1+8-10=-1=d^6(4). \]
  • Il nodo \(3\) si ripete: la passeggiata contiene il ciclo \(3,5,4,3\), di lunghezza \(-1\) (in rosso).

Figura 5

L'algoritmo di Bellman–Ford calcola \(d^k\), le passeggiate minime con al più \(k\) archi, in tempo \(O(n\,m)\). Senza cicli negativi raggiungibili da \(s\) si ferma entro \(n\) passate con le distanze; un cambiamento nella passata \(n\) rivela un ciclo negativo, che si trova leggendo i predecessori all'indietro.


Avanti: 3.6 L'algoritmo di Dijkstra