Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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:

  1. 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;
  2. 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.

  1. Ad ogni iterazione si etichetta permanentemente un nodo.
  2. 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.
  3. 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. \]

I materiali di supporto della lezione

D. Bertsimas e J.N. Tsitsiklis, Introduction to Linear Optimization, Belmont - Massachusetts (USA), Dynamic Ideas and Athena Scientific, 2008.

M. Fischetti, Lezioni di Ricerca Operativa, Padova, Edizioni Libreria Progetto Padova, 1999.

S. Martello, Fondamenti di Ricerca Operativa L-A, Bologna, Società Editrice Esculapio, 2004.

S. Martello, Ricerca Operativa LS, Bologna, Società Editrice Esculapio, 2004.

Dispense del Corso di Ricerca Operativa presso l'Università degli Studi di Pisa.

Dispense ed Appunti del Corso prodotte da Paola Festa.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion