Home

Federica EU

1/7

Paola Festa » 22.Problemi di Cammino Minimo: algoritmo di Dijkstra

Algoritmo di Dijkstra, 1

L’algoritmo di Dijkstra risolve il problema SPP ed il problema SPT in un grafo G=(V,A), tale che $c_{ij}\geq 0,\ \forall (i,j)\in A$ (G non può contenere cicli di costo negativo).

L’algoritmo di Dijkstra si basa sul contenuto di un importante teorema di cui riportiamo di seguito l’enunciato.

Teorema. Sia G=(V,A) un grafo orientato. Sia S un sottoinsieme proprio di V, s in S e per ogni i in S, sia L[i] il costo del cammino minimo da s ad i (L[s]=0).
Sia, inoltre,
$(v,h)=\mbox{argmin}\ \{L[i]+c_{ij}\ \vert\ (i,j)\in \delta_G^+(S)\}.$
Se $c_{ij}\geq 0, \forall (i,j)\in A$ , allora $L[v]+c_{vh}=L[h]$ .

Algoritmo di Dijkstra, 2

L’algoritmo di Dijkstra usa un array di etichette L[n].

Durante la computazione l’insieme V è partizionato in due sottoinsiemi:

S, che contiene i nodi con etichetta permanente, cioè i nodi i per i quali l’etichetta L[i] esprime il costo di un cammino minimo da s ad i;
$V\setminus S$ , che contiene i nodi j per i quali L[j] costituisce un’etichetta temporanea, cioè esprime un limite superiore sul costo di un cammino minimo da s a j.

Inizialmente, solo il nodo origine s è etichettato permanentemente e la sua etichetta permanente vale 0.
Tutti gli altri nodi hanno etichetta temporanea che vale $+\infty$ e sono memorizzati in una lista Q.

Ad ogni iterazione l’algoritmo rimuove da Q il nodo i corrispondente all’etichetta temporanea minima che diventa permanente (grazie alla validità del Teorema) e poi esplora la stella uscente FS(i) di i, al fine di eventualmente migliorare l’etichetta temporanea dei nodi adiacenti ad i.

Algoritmo di Dijkstra, 3

$\fbox{\begin{minipage}[h]{7cm} \footnotesize{ \begin{tt} {\bf algoritmo} {dijkstra}($V$,$A$,$s$) \\ $1$\hspace*{0.5truecm} $Q:=V$; $L[s]:=0$; $p_s:=s$; \\ $2$\hspace*{0.5truecm} {\bf for each} $j\in V\setminus\{s\}$ {\bf do} \\ $3$\hspace*{1truecm} $L[j]:=+\infty$; $p_j:=0$; \\ $4$\hspace*{0.5truecm} {\bf endfor}\\ $5$\hspace {0.5truecm} {\bf while} ($Q\not=\emptyset$) {\bf do} \\ $6$\hspace*{1truecm} $i:=$arg$\displaystyle{\min_{j\in Q}\{L[j]\}}$; $Q:=Q\setminus\{i\}$;\\ $7$\hspace*{1truecm} {\bf for each} ($j\in FS(i)$) {\bf do} \\ $8$\hspace*{1.5truecm} {\bf if} ($L[j]>L[i]+c_{ij}$) {\bf then} \\ $9$\hspace {2truecm} $L[j]:=L[i]+c_{ij}$; \\ $10$\hspace*{2truecm} $p_j:=i$; \\ $11$\hspace*{1.3truecm} {\bf endif} \\ $12$\hspace*{0.8truecm} {\bf endfor} \\ $13$\hspace*{0.3truecm} {\bf endwhile} \\ $14$\hspace*{0.3truecm} {\bf return} ($L$,$p$); \\ {\bf end} {dijkstra} \end{tt} } \end{minipage}}$

Algoritmo di Dijkstra, 4

Note.

Ad ogni iterazione si etichetta permanentemente un nodo.
Ad ogni iterazione $\delta_G^+(S)$ è costituito da quegli archi che collegano i nodi di S ai nodi etichettati temporaneamente, ossia ai nodi di Q con etichetta finita.
Nel caso si voglia individuare un cammino minimo dal nodo origine s ad un nodo destinazione d, allora l’algoritmo di Dijkstra termina quando il nodo d viene estratto da Q.

Complessità computazionale dell’algoritmo di Dijkstra

L’inizializzazione dell’array dei predecessori e dell’array delle etichette temporanee dei nodi (loop for 2–4) richiede
$O(\vert V\vert)=O(n).$

Il loop while (linee 5–13) richiede $O(n)$ e ad ogni sua iterazione l’individuazione in Q del nodo i avente etichetta minima richiede $O(n)$ , mentre l’esplorazione di FS(i) richiede $O(\vert FS(i)\vert)$ .

Ne consegue che la complessità dell’algoritmo di Dijkstra è
$O(n^2+m).$

Algoritmo di Dijkstra con heap binario

In letteratura esistono diverse implementazioni dell’algoritmo di Dijkstra che si differenziano tra loro per la scelta della particolare struttura dati da adoperare per rappresentare Q.

Una di esse, ad esempio, implementa Q come heap binario.

In tal caso, in fase di inizializzazione occorre costruire l’heap Q.

Ad ogni iterazione

l’estrazione del nodo i=Q[1] avviene in tempo costante, ma all’estrazione deve seguire un’operazione di re-heapificazione di Q e tale operazione costa $O(\log n)$ ;
viene ispezionata la stella uscente FS(i) e per ogni nodo j adiacente ad i per cui migliora l’etichetta temporanea L[j] occorre aggiornare la posizione di j nell’heap Q.

Dunque, la complessità totale diventa
$O(m\log n).$

Algoritmo di Dijkstra con array di buckets

In un’altra interessante implementazione, nota come implementazione di Dial, Q è un array cha ha un numero di elementi pari al massimo numero di differenti valori che un’etichetta temporanea può assumere, cioè
$\[(n-1)\cdot c_{\mbox{max}}+1,\ \mbox{dove}\ c_{\mbox{max}}=\displaystyle{\max_{(i,j)\in A}c_{ij}}.\]<br />$
Ogni entrata Q[k] è chiamata bucket ed è una lista doppiamente puntata contenente tutti i nodi la cui etichetta temporanea ha valore k.

E’ semplice verificare che l’ implementazione di Dial ha complessità pseudopolinomiale pari a
$O(m+n\cdot c_{\mbox{max}}).$

Lo spazio di memoria che essa richiede è molto grande, ma può facilmente essere ridotta a $c_{\mbox{max}}+1$ , stabilendo che un nodo j viene memorizzato nel bucket Q[k] se
$L[j]\ \mbox{mod}\ (c_{\mbox{max}}+1)=k.$