3.2 Condizioni di ottimalità e potenziali¶
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.7: potenziali e costi ridotti
Un vettore \(\vet{\pi} \in \R^n\) assegna un potenziale \(\pi_i\) a ogni nodo \(i \in N\). Il costo ridotto dell'arco \((i,j)\) rispetto a \(\vet{\pi}\) è
I potenziali sono ammissibili se \(\bar{c}_{ij} \ge 0\) per ogni arco \((i,j) \in A\), e un arco con \(\bar{c}_{ij}=0\) è stretto.
-
Date delle etichette \(d(j)\), lunghezze di passeggiate da \(s\) a \(j\), usiamo i potenziali \(\pi_i=-d(i)\). Allora \(\bar{c}_{ij}=d_{ij}+d(i)-d(j)\), e i potenziali sono ammissibili se e solo se \(d(j) \le d(i)+d_{ij}\) per ogni arco.
-
Lungo una passeggiata \(W=i_0,i_1,\dots,i_k\) i potenziali si elidono a catena (somma telescopica):
\[ d(W)=\sum_{t=1}^{k} \bar{c}_{i_{t-1}i_t} \;+\; \pi_{i_0}-\pi_{i_k} . \]
Teorema 3.8: potenziali come certificato di ottimalità
Siano \(\vet{\pi}\) potenziali ammissibili e sia \(P\) un cammino da \(s\) a \(t\) i cui archi sono tutti stretti. Allora \(P\) è un cammino minimo da \(s\) a \(t\), e \(d(P)=\pi_s-\pi_t\). Inoltre \(G\) non ha cicli negativi.
Dimostrazione
Usiamo la formula telescopica qui sopra.
-
Gli archi di \(P\) hanno \(\bar{c}_{ij}=0\), quindi \(d(P)=\pi_s-\pi_t\).
-
Per ogni cammino \(Q\) da \(s\) a \(t\), \(d(Q)=\sum_{(i,j) \in Q}\bar{c}_{ij}+\pi_s-\pi_t \ge \pi_s-\pi_t=d(P)\).
-
Per ogni ciclo \(C\) il primo e l'ultimo nodo coincidono, quindi \(d(C)=\sum_{(i,j) \in C}\bar{c}_{ij} \ge 0\). □
Corollario 3.9: condizioni di ottimalità per le etichette
Siano le etichette \(d(j)\), \(j \in N\), finite con \(d(s)=0\), e supponiamo che
-
(i) \(d(j) \le d(i)+d_{ij}\) per ogni arco \((i,j) \in A\);
-
(ii) per ogni \(j \neq s\) esista un cammino da \(s\) a \(j\) di lunghezza \(d(j)\).
Allora \(d(j)=\tilde{d}(j)\) per ogni \(j \in N\).
Dimostrazione
Per (i) i potenziali \(\pi_i=-d(i)\) sono ammissibili, quindi ogni cammino \(Q\) da \(s\) a \(j\) ha \(d(Q) \ge \pi_s-\pi_j=d(j)\) con il ragionamento del Teorema 3.8. Per (ii) il valore \(d(j)\) è realizzato da un cammino, quindi \(d(j)=\tilde{d}(j)\). □
Esempio 3.4: un certificato sul grafo di riferimento
Con le distanze dell'Esempio 3.1 i potenziali sono \(\vet{\pi}=-\tilde{\vet{d}}=(0,-5,-2,-8,-10, -13)\), e i costi ridotti \(\bar{c}_{ij}=d_{ij}-\pi_i+\pi_j\) sono:
| arco | \((1,2)\) | \((1,3)\) | \((2,4)\) | \((3,2)\) | \((3,5)\) | \((4,3)\) | \((4,6)\) | \((5,4)\) | \((5,6)\) |
|---|---|---|---|---|---|---|---|---|---|
| \(d_{ij}\) | \(7\) | \(2\) | \(3\) | \(3\) | \(8\) | \(1\) | \(5\) | \(2\) | \(7\) |
| \(\bar{c}_{ij}\) | \(2\) | \(0\) | \(0\) | \(0\) | \(0\) | \(7\) | \(0\) | \(4\) | \(4\) |
-
Tutti i costi ridotti sono non negativi, e gli archi stretti sono gli archi dell'albero dei cammini minimi. Il cammino \(1,3,2,4,6\) è stretto, quindi è minimo, con lunghezza \(\pi_1-\pi_6=13\).
-
L'albero della visita in ampiezza, \((1,2)\), \((1,3)\), \((2,4)\), \((3,5)\), \((4,6)\), dà le etichette \((0,7,2,10,10,15)\). Con i loro potenziali, \(\bar{c}_{32}=3-(-2)+(-7)=-2<0\): i potenziali non sono ammissibili, ed entrare nel nodo \(2\) attraverso \((3,2)\) accorcia il suo cammino di \(2\).
Potenziali ammissibili (\(\bar{c}_{ij}=d_{ij}-\pi_i+\pi_j \ge 0\) su ogni arco) e un cammino fatto di archi stretti dimostrano che il cammino è minimo. Con le etichette, \(\pi_i=-d(i)\), e l'ammissibilità si legge \(d(j) \le d(i)+d_{ij}\).