3.6 L'algoritmo di Dijkstra¶
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
-
In questa sezione tutte le lunghezze sono non negative: \(d_{ij} \ge 0\) per ogni arco. Allora ogni ciclo ha lunghezza \(\ge 0\), e vale (A2).
-
I nodi sono permanenti, quando la loro etichetta è definitiva, oppure temporanei. A ogni iterazione il nodo temporaneo con l'etichetta minima diventa permanente.
Algoritmo: Algoritmo di Dijkstra
STOP.Teorema 3.22: correttezza dell'algoritmo di Dijkstra
Se \(d_{ij} \ge 0\) per ogni arco, a ogni iterazione dell'algoritmo di Dijkstra:
-
(a) ogni nodo permanente \(i\) ha \(d(i)=\tilde{d}(i)\);
-
(b) ogni nodo temporaneo \(j\) ha come \(d(j)\) la lunghezza minima di un cammino da \(s\) a \(j\) i cui nodi diversi da \(j\) sono tutti permanenti (\(+\infty\) se non ce n'è nessuno).
All'arresto, \(d(j)=\tilde{d}(j)\) per ogni \(j \in N\).
Dimostrazione
Entrambe le proprietà valgono dopo il Passo 0, quando non ci sono nodi permanenti. Sia \(i\) il nodo scelto al Passo 1.
-
\(d(i)=\tilde{d}(i)\). Sia \(P\) un cammino qualsiasi da \(s\) a \(i\), e sia \(h\) il suo primo nodo temporaneo. Il tratto di \(P\) fino a \(h\) ha lunghezza \(\ge d(h)\) per (b), e il resto ha lunghezza \(\ge 0\), perché \(d \ge 0\). Quindi \(d(P) \ge d(h) \ge d(i)\), e per (b) il valore \(d(i)\) è la lunghezza di un cammino: \(d(i)=\tilde{d}(i)\).
-
(b) dopo il Passo 2. Sia \(j\) temporaneo e \(Q\) un cammino verso \(j\) i cui altri nodi sono permanenti, e sia \(h\) il nodo che precede \(j\). Se \(h=i\), allora \(d(Q) \ge \tilde{d}(i)+d_{ij}=d(i)+d_{ij}\), il valore controllato al Passo 2.
-
Se \(h \neq i\), allora \(h\) è diventato permanente prima di \(i\), attraverso un cammino di nodi permanenti di lunghezza \(\tilde{d}(h)\); quando \(h\) è stato scelto, il Passo 2 ha dato \(d(j) \le \tilde{d}(h)+d_{hj} \le d(Q)\).
Quindi il nuovo minimo è \(\min\{d(j),\,d(i)+d_{ij}\}\), realizzato da un cammino, ed è l'etichetta lasciata dal Passo 2. All'arresto, i nodi temporanei hanno \(d(j)=+\infty\): per (b) nessun arco va dall'insieme dei nodi permanenti verso di loro, quindi non sono raggiungibili e \(\tilde{d}(j)=+\infty\). □
-
Per il problema \(s\)–\(t\) l'algoritmo può fermarsi appena \(t\) diventa permanente, per (a).
-
Gli archi \((\mathit{pred}(j),j)\) formano un albero dei cammini minimi: \(\mathit{pred}(j)\) diventa permanente prima di \(j\), e quando viene posto per l'ultima volta vale \(d(j)=d(\mathit{pred}(j))+d_{\mathit{pred}(j)\,j}\), con entrambe le etichette definitive.
Teorema 3.23: tempo di esecuzione dell'algoritmo di Dijkstra
Con le etichette in un vettore, l'algoritmo di Dijkstra richiede tempo \(O(n^2)\).
Dimostrazione
Le iterazioni sono al più \(n\), e il Passo 1 esamina le etichette temporanee in tempo \(O(n)\). Il Passo 2 esamina la stella uscente del nodo scelto, e ogni nodo viene scelto una volta, quindi tutti gli aggiornamenti richiedono tempo \(O(m)\). Il totale è \(O(n^2+m)=O(n^2)\), perché \(m \le n(n-1)\). □
- Con le etichette temporanee in un heap binario, il Passo 1 e ogni diminuzione di un'etichetta richiedono tempo \(O(\log n)\): il totale è \(O((n+m)\log n)\), migliore di \(O(n^2)\) sui grafi sparsi.
3.6.1 L'algoritmo di Dijkstra sul grafo di riferimento¶
Esempio 3.9: Dijkstra dal nodo \(1\)
Eseguiamo l'algoritmo con le lunghezze dell'Esempio 3.1. Ogni riga è un'iterazione: il nodo scelto diventa permanente (etichetta in grassetto), e accanto a un'etichetta che è diminuita c'è, tra parentesi, il nuovo predecessore.
| iterazione | nodo scelto \(i\) | \(d(1)\) | \(d(2)\) | \(d(3)\) | \(d(4)\) | \(d(5)\) | \(d(6)\) |
|---|---|---|---|---|---|---|---|
| \(1\) | \(1\) | \(\mathbf{0}\) | \(7\) (\(1\)) | \(2\) (\(1\)) | \(\infty\) | \(\infty\) | \(\infty\) |
| \(2\) | \(3\) | \(\mathbf{0}\) | \(5\) (\(3\)) | \(\mathbf{2}\) | \(\infty\) | \(10\) (\(3\)) | \(\infty\) |
| \(3\) | \(2\) | \(\mathbf{0}\) | \(\mathbf{5}\) | \(\mathbf{2}\) | \(8\) (\(2\)) | \(10\) | \(\infty\) |
| \(4\) | \(4\) | \(\mathbf{0}\) | \(\mathbf{5}\) | \(\mathbf{2}\) | \(\mathbf{8}\) | \(10\) | \(13\) (\(4\)) |
| \(5\) | \(5\) | \(\mathbf{0}\) | \(\mathbf{5}\) | \(\mathbf{2}\) | \(\mathbf{8}\) | \(\mathbf{10}\) | \(13\) |
| \(6\) | \(6\) | \(\mathbf{0}\) | \(\mathbf{5}\) | \(\mathbf{2}\) | \(\mathbf{8}\) | \(\mathbf{10}\) | \(\mathbf{13}\) |
-
Nell'iterazione \(2\) l'etichetta del nodo \(2\) scende da \(7\) a \(2+3=5\); nell'iterazione \(5\) l'arco \((5,6)\) offre \(10+7=17>13\), e l'arco \((5,4)\) termina in un nodo permanente.
-
I nodi diventano permanenti nell'ordine \(1,3,2,4,5,6\), con \(\tilde{d}=(0,5,2,8,10,13)\); i predecessori danno l'albero dei cammini minimi dell'Esempio 3.3.
3.6.2 Lunghezze negative¶
Esempio 3.10: un arco negativo fa fallire l'algoritmo di Dijkstra
Nel grafo qui sotto, con \(s=1\), l'algoritmo rende permanente il nodo \(2\) con \(d(2)=2\), poi il nodo \(3\) con \(d(3)=3\); l'arco \((3,2)\) termina in un nodo permanente e viene ignorato. Il cammino \(1,3,2\) ha lunghezza \(3-2=1<2\).
Sul grafo di riferimento con le lunghezze \(d'\) dell'Esempio 3.7 (\(d'_{54}=-3\)), l'algoritmo di Dijkstra rende permanenti i nodi nell'ordine \(1,3,2,4,5,6\) e restituisce \(d(4)=8\) e \(d(6)=13\): il nodo \(4\) diventa permanente prima del nodo \(5\), quindi il cammino più corto \(1,3,5,4\), di lunghezza \(7\), sfugge all'algoritmo, e con esso il cammino verso \(6\) di lunghezza \(12\).
- La dimostrazione del Teorema 3.22 usa \(d \ge 0\) in un solo punto: il resto di \(P\) dopo il suo primo nodo temporaneo ha lunghezza \(\ge 0\). Un arco negativo invalida proprio questo punto.
Con lunghezze non negative, l'algoritmo di Dijkstra rende permanente, a ogni iterazione, il nodo temporaneo con l'etichetta minima, che da quel momento è definitiva; richiede tempo \(O(n^2)\). Con un arco negativo può sbagliare, e si usa invece l'algoritmo di Bellman–Ford.
3.7 Errori tipici¶
Attenzione
-
Eseguire l'algoritmo di Dijkstra con un arco negativo. Le sue etichette possono essere sbagliate, come con \(d'_{54}=-3\) sul grafo di riferimento; usare Bellman–Ford, oppure l'ordine topologico se il grafo è aciclico.
-
Sommare una costante a ogni lunghezza. Rende le lunghezze non negative ma cambia i cammini minimi: un cammino con \(k\) archi cresce di \(k\) volte la costante.
-
Invertire il segno dei potenziali. Con \(+1\) nella coda di \(\mat{B}\) i vincoli duali sono \(\pi_i-\pi_j \le d_{ij}\) e i potenziali ottimi sono \(\pi_i=-\tilde{d}(i)\).
-
Saltare il test della passata \(n\). Dopo \(n-1\) passate le etichette sono le distanze solo in assenza di cicli negativi; un cambiamento nella passata \(n\) ne rivela uno.
-
Aspettarsi che Bellman–Ford veda ogni ciclo negativo. Rileva solo i cicli raggiungibili da \(s\), mentre un ciclo negativo in un punto qualsiasi di \(G\) rende illimitato il modello LP.
-
Aggiornare un nodo permanente nell'algoritmo di Dijkstra. La sua etichetta è definitiva; si aggiornano solo i nodi temporanei.
-
Cercare un ordine topologico in un grafo con cicli. Esiste solo nei grafi aciclici: il grafo di riferimento non ne ha.
3.8 In sintesi¶
In sintesi
-
La distanza \(\tilde{d}(j)\) è la lunghezza di un cammino minimo da \(s\) a \(j\); è ben definita quando nessun ciclo negativo è raggiungibile da \(s\) (A2).
-
I sottocammini dei cammini minimi sono minimi; le distanze soddisfano le equazioni di Bellman, ed esiste un albero dei cammini minimi.
-
Potenziali ammissibili, \(\bar{c}_{ij}=d_{ij}-\pi_i+\pi_j \ge 0\), e un cammino di archi stretti certificano l'ottimalità.
-
Il modello LP è un flusso unitario, \(\mat{B}\vet{x}=\vet{b}\), \(\vet{x} \ge \vet{0}\); il suo duale è \(\max\{\pi_s-\pi_t : \pi_i-\pi_j \le d_{ij}\}\), con ottimo in \(\pi_i=-\tilde{d}(i)\).
-
Grafi aciclici: ordine topologico, \(O(n+m)\), lunghezze qualsiasi. Bellman–Ford: \(O(n\,m)\), lunghezze qualsiasi, rileva i cicli negativi. Dijkstra: \(O(n^2)\), lunghezze non negative.
Il grafo di riferimento in breve.
| lunghezze \(d\) (Dijkstra) | \(\tilde{d}=(0,5,2,8,10,13)\), ordine \(1,3,2,4,5,6\) |
| modelli LP | \(z(\mathrm{SP}(1,6))=13\), \(z(\mathrm{SP}(1))=38\) |
| lunghezze \(d'\), \(d'_{54}=-3\) (Bellman–Ford) | \(\tilde{d}=(0,5,2,7,10,12)\), \(5\) passate |
| lunghezze \(d''\), \(d''_{54}=-10\) | ciclo negativo \(3,5,4,3\) di lunghezza \(-1\) |
| grafo aciclico, arco \((3,4)\) | ordine \(1,3,2,5,4,6\); \(\tilde{d}=(0,5,2,3,10,8)\) |
Esercizi su questo capitolo: Cammini minimi