Vai al contenuto

3.6 L'algoritmo di Dijkstra

  • 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

Input: un grafo orientato \(G=(N,A)\) con lunghezze \(d_{ij} \ge 0\), una sorgente \(s \in N\)
Output: le distanze \(d(j)=\tilde{d}(j)\) e i predecessori \(\mathit{pred}(j)\)
1Passo 0 (inizializzazione). Porre \(d(s):=0\), \(d(j):=+\infty\) per \(j \neq s\); tutti i nodi sono temporanei.
2Passo 1 (selezione). Se nessun nodo temporaneo ha un'etichetta finita, STOP.
3 Altrimenti rendere permanente il nodo temporaneo \(i\) con \(d(i)\) minima (quello di indice minimo, se ce n'è più di uno).
4Passo 2 (aggiornamento). Per ogni arco \((i,j) \in \delta^+(i)\) con \(j\) temporaneo: se \(d(i)+d_{ij}<d(j)\), porre \(d(j):=d(i)+d_{ij}\) e \(\mathit{pred}(j):=i\).
5 Andare al Passo 1.

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.

  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)\).

  2. (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.

  3. 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\).

Figura 6

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