3.5 L'algoritmo di Bellman–Ford¶
Parte 2 · Alberi e cammini · Capitolo 3 · Capitolo 3: Cammini minimi · Dispensa, volume 2 (PDF) · Slide · Esercizi: Cammini minimi · App: Cammini minimi: Dijkstra, Bellman–Ford, grafi aciclici
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\)
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
STOP: \(\tilde{d}=d^k\).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)\).
-
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)\).
-
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\).
-
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)\).
-
\(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)\).
-
Nella passata \(t(j)\), \(d(j)=d^{t(j)-1}(p)+d_{pj} \ge d(p)+d_{pj}\), perché le etichette non aumentano mai.
-
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)\).
-
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:
-
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\).
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:
-
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).
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