3.6 Algoritmo di Dijkstra

Parte 2 · Alberi e cammini · Capitolo 3 · Capitolo 3: Cammini minimi · Dispensa, volume 2 (PDF) · 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. Quindi ogni ciclo ha una lunghezza \(\ge 0\) e (A2) sono validi.

• I nodi sono permanente, quando la loro etichetta è definitiva, o temporaneo. Ad ogni iterazione il il nodo temporaneo con l'etichetta più piccola diventa permanente.

Algoritmo: Algoritmo di Dijkstra

Input: un grafo diretto \(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)\)

1Passaggio 0 (inizializzazione). Imposta \(d(s):=0\), \(d(j):=+\infty\) per \(j \neq s\); tutti i nodi sono temporanei.

2Passaggio 1 (selezione). Se nessun nodo temporaneo ha un'etichetta finita, STOP.

3 Altrimenti rendere permanente il nodo temporaneo \(i\) con il più piccolo \(d(i)\) (l'indice più piccolo, se superiore a uno).

4Passaggio 2 (aggiornamento). Per ogni arco \((i,j) \in \delta^+(i)\) con \(j\) temporaneo: se \(d(i)+d_{ij}<d(j)\), impostare \(d(j):=d(i)+d_{ij}\) e \(\mathit{pred}(j):=i\).

5 Vai al passaggio 1.

Teorema 3.22: correttezza dell'algoritmo di Dijkstra

Se \(d_{ij} \ge 0\) per ogni arco, ad 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 percorso da \(s\) a \(j\) i cui nodi diversi da \(j\) sono tutti permanenti (\(+\infty\) se non ce n'è nessuno).

Alla fermata, \(d(j)=\tilde{d}(j)\) per ogni \(j \in N\).

Dimostrazione

Entrambe le proprietà restano valide dopo il passaggio 0, senza nodo permanente. Lascia che \(i\) sia il nodo selezionato nel passaggio 1.

1. \(d(i)=\tilde{d}(i)\). Sia \(P\) un percorso qualsiasi da \(s\) a \(i\) e \(h\) sia il suo primo nodo temporaneo. Il parte di \(P\) fino a \(h\) ha lunghezza \(\ge d(h)\) di (b) e il resto ha lunghezza \(\ge 0\), a partire da \(d \ge 0\). Quindi \(d(P) \ge d(h) \ge d(i)\) e per (b) il valore \(d(i)\) è la lunghezza di un percorso: \(d(i)=\tilde{d}(i)\).

2. (b) dopo il passo 2. Sia \(j\) temporaneo e \(Q\) un percorso verso \(j\) i cui altri nodi siano permanenti, con \(h\) il nodo prima di \(j\). Se \(h=i\), allora \(d(Q) \ge \tilde{d}(i)+d_{ij}=d(i)+d_{ij}\), il valore testato nel passaggio 2.

3. Se \(h \neq i\), allora \(h\) diventava permanente prima di \(i\), attraverso un percorso di nodi permanenti di lunghezza \(\tilde{d}(h)\); quando è stato selezionato \(h\), il passaggio 2 ha prodotto \(d(j) \le \tilde{d}(h)+d_{hj} \le d(Q)\).

Quindi il nuovo minimo è \(\min\{d(j),\,d(i)+d_{ij}\}\), raggiunto da un percorso, che è l'etichetta lasciata dal passaggio 2. Alla fermata, i nodi temporanei hanno \(d(j)=+\infty\): per (b) nessun arco lascia il permanente impostato verso di loro, quindi non sono raggiungibili e \(\tilde{d}(j)=+\infty\). □

• Per il problema \(s\)–\(t\) l'algoritmo può interrompersi non appena \(t\) è permanente, mediante (a).

• Gli archi \((\mathit{pred}(j),j)\) formano un albero del percorso più breve: \(\mathit{pred}(j)\) è permanente prima di \(j\) e quando viene impostato l'ultima volta \(d(j)=d(\mathit{pred}(j))+d_{\mathit{pred}(j)\,j}\) con entrambe le etichette finali.

Teorema 3.23: tempo di esecuzione dell'algoritmo di Dijkstra

Con le etichette in un array, l'algoritmo di Dijkstra viene eseguito nel tempo \(O(n^2)\).

Dimostrazione

Esistono al massimo le iterazioni \(n\) e il passaggio 1 esegue la scansione delle etichette temporanee nel tempo \(O(n)\). Il passaggio 2 esegue la scansione dell'inoltro stella del nodo selezionato e ciascun nodo viene selezionato una volta, quindi tutti gli aggiornamenti richiedono tempo \(O(m)\). Il totale è \(O(n^2+m)=O(n^2)\), da \(m \le n(n-1)\). □

• Con le etichette temporanee in un heap binario, il passaggio 1 e ogni diminuzione di un'etichetta richiedono tempo \(O(\log n)\): il il totale è \(O((n+m)\log n)\), migliore di \(O(n^2)\) su grafi sparsi.

3.6.1 Algoritmo di Dijkstra sul grafo di riferimento

Esempio 3.9: Dijkstra dal nodo \(1\)

Eseguiamo l'algoritmo con le lunghezze Esempio 3.1. Ogni riga è un'iterazione: il nodo selezionato diventa permanente (etichetta in grassetto) e un'etichetta diminuita ha il nuovo predecessore tra parentesi.

iterazione e \(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 con un nodo permanente.

• I nodi diventano permanenti nell'ordine \(1,3,2,4,5,6\), con \(\tilde{d}=(0,5,2,8,10,13)\); danno i predecessori l'albero del percorso più breve di Esempio 3.3.

3.6.2 Lunghezze negative

Esempio 3.10: un arco negativo interrompe l'algoritmo di Dijkstra

Nel grafo sottostante, con \(s=1\), l'algoritmo rende permanente il nodo \(2\) con \(d(2)=2\), quindi il nodo \(3\) con \(d(3)=3\); l'arco \((3,2)\) termina con un nodo permanente e viene ignorato. Il percorso \(1,3,2\) ha lunghezza \(3-2=1<2\).

Sul grafo di riferimento con le lunghezze \(d'\) di 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\) è permanente prima nodo \(5\), quindi il percorso più breve \(1,3,5,4\) di lunghezza \(7\) viene perso e con esso il percorso verso \(6\) di lunghezza \(12\).

• La dimostrazione di Teorema 3.22 utilizza \(d \ge 0\) in un punto: il resto di \(P\) dopo il suo primo nodo temporaneo ha lunghezza \(\ge 0\). Un arco negativo interrompe esattamente questo passaggio.

Con lunghezze non negative, l'algoritmo di Dijkstra rende permanente, ad ogni iterazione, il nodo temporaneo con il etichetta più piccola, la cui etichetta è quindi definitiva; funziona in tempo \(O(n^2)\). Con un arco negativo può fallire e il Viene invece utilizzato l'algoritmo Bellman–Ford.

3.7 Errori tipici

Attenzione

• Esecuzione dell'algoritmo di Dijkstra con un arco negativo. Le sue etichette possono essere errate, come con \(d'_{54}=-3\) su il grafo di riferimento; utilizzare Bellman–Ford o l'ordine topologico se il grafo è aciclico.

• Aggiungere una costante a ogni lunghezza. Rende le lunghezze non negative ma modifica i percorsi più brevi: un percorso con archi \(k\) cresce di \(k\) volte la costante.

• Scambio di segno dei potenziali. Con \(+1\) nella coda di \(\mat{B}\) i vincoli duali sono \(\pi_i-\pi_j \le d_{ij}\) e i potenziali ottimali sono \(\pi_i=-\tilde{d}(i)\).

• Saltare il test di passaggio \(n\). Dopo che \(n-1\) ha superato le etichette sono solo le distanze senza negativo cicli; un cambiamento nel passaggio \(n\) ne rivela uno.

• Mi aspetto che Bellman–Ford veda ogni ciclo negativo. Rileva solo i cicli raggiungibili da \(s\), mentre un ciclo negativo ovunque in \(G\) rende il modello LP illimitato.

• Aggiornamento di un nodo permanente nell'algoritmo di Dijkstra. La sua etichetta è definitiva; lo sono solo i nodi temporanei aggiornato.

• Ricerca di un ordine topologico in un grafo con cicli. Esiste solo nei grafi aciclici: il il grafo di riferimento non ne ha nessuno.

3.8 In sintesi

In sintesi

• La distanza \(\tilde{d}(j)\) è la lunghezza del percorso più breve da \(s\) a \(j\); è ben definito quando no il ciclo negativo è raggiungibile da \(s\) (A2).

• I sottopercorsi dei percorsi più brevi sono i più brevi; le distanze soddisfano le equazioni di Bellman e un albero dei cammini più brevi esiste.

• I potenziali fattibili, \(\bar{c}_{ij}=d_{ij}-\pi_i+\pi_j \ge 0\) e un percorso di archi stretti certificano l'ottimalità.

• Il modello LP è un'unità di flusso, \(\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}\}\), ottimale su \(\pi_i=-\tilde{d}(i)\).

• Grafi aciclici: ordine topologico, \(O(n+m)\), qualsiasi lunghezza. Bellman–Ford: \(O(n\,m)\), qualsiasi lunghezza, rileva cicli negativi. Dijkstra: \(O(n^2)\), lunghezze non negative.

Il grafo di riferimento in sintesi.

lunghezze \(d\) (Dijkstra) e \(\tilde{d}=(0,5,2,8,10,13)\), ordinare \(1,3,2,4,5,6\)

Modelli LP e \(z(\mathrm{SP}(1,6))=13\), \(z(\mathrm{SP}(1))=38\)

lunghezze \(d'\), \(d'_{54}=-3\) (Bellman–Ford) e \(\tilde{d}=(0,5,2,7,10,12)\), \(5\) passa

lunghezze \(d''\), \(d''_{54}=-10\) e ciclo negativo \(3,5,4,3\) della lunghezza \(-1\)

grafo aciclico, arco \((3,4)\) e ordine \(1,3,2,5,4,6\); \(\tilde{d}=(0,5,2,3,10,8)\)

---

Esercizi su questo capitolo: Cammini minimi