Algoritmo di Dijkstra: differenze tra le versioni

Versione delle 13:25, 9 gen 2018

Versione delle 13:25, 9 gen 2018

Riga 1:

{{Avvisounicode}}

{{nota disambigua|l'algoritmo per la [[mutua esclusione]] in sistemi concorrenti, detto anche "algoritmo di proiezione di Dijkstra"|la voce [[algoritmo di Dekker]]}}

{{

{{Algoritmo

|classe = [[Algoritmo di ricerca]]

|immagine = Dijkstra Animation.gif

|didascalia = Esecuzione dell'algoritmo di Dijkstra

|struttura dati = [[Grafo]]

|tempo = <math>O(|E| + |V| \log|V|)</math><ref>[http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=715934 IEEE Xplore - Fibonacci Heaps And Their Uses In Improved Network Optimization Algorithms<!-- Titolo generato automaticamente -->]</ref>

|tempo migliore =

|tempo medio =

|spazio =

|ottimale =

|completo =

}}

L<nowiki>'</nowiki>'''algoritmo di Dijkstra''' è un algoritmo utilizzato per cercare i [[cammini minimi]] in un [[grafo]] con o senza ordinamento, ciclico e con pesi non negativi sugli archi. Fu inventato nel 1956 dall'informatico olandese [[Edsger Dijkstra]] che lo pubblicò successivamente nel 1959.

Tale algoritmo trova applicazione in molteplici contesti quale l'ottimizzazione nella realizzazioni di reti (idriche, [[telecomunicazioni]], stradali, circuitali, ecc.) o l'organizzazione e la valutazione di percorsi runtime nel campo della [[robotica]].

== Algoritmo ==

Supponiamo di avere un grafo con n vertici contraddistinti da numeri interi {1,2,...,n} e che 1 sia scelto come nodo di partenza. Il peso sull'arco che congiunge i nodi j e k è indicato con ''p(j,k)''. Ad ogni nodo, al termine dell'analisi, devono essere associate due etichette, ''f(i)'' che indica il peso totale del cammino (la somma dei pesi sugli archi percorsi per arrivare al nodo i-esimo) e ''J(i)'' che indica il nodo che precede i nel cammino minimo. Inoltre definiamo due insiemi ''S'' e ''T'' che contengono rispettivamente i nodi a cui sono già state assegnate le etichette e quelli ancora da scandire.

# ''Inizializzazione''.

#* Poniamo ''S''={1}, ''T''={2,3,...,n}, f(1)=0, J(1)=0.

#* Poniamo f(i)=p(1,i), J(i)=1 per tutti i nodi adiacenti ad 1.

#* Poniamo f(i)= ∞, per tutti gli altri nodi.

# ''Assegnazione etichetta permanente''

#* Se f(i)= ∞ per ogni i in T '''STOP'''

#* Troviamo j in T tale che f(j)=min f(i) con i appartenente a T

#* Poniamo T=T<math>\setminus</math>{j} e S=S∪{j}

#* Se T=Ø '''STOP'''

# ''Assegnazione etichetta provvisoria''

#* Per ogni i in T, adiacente a j e tale che f(i)>f(j)+p(j,i) poniamo:

#** f(i)=f(j)+p(j,i)

#** J(i)=j

#* Andiamo al passo 2

==Pseudocodice==

Nel seguente algoritmo, il codice <code>u := vertici in ''Q'' con la più breve dist[]</code>, cerca per dei vertici <code><var>u</var></code> nell'insieme dei vertici <code><var>Q</var></code> che hanno il valore <code>dist[<var>u</var>]</code> più piccolo. Questi vertici sono rimossi dall'insieme <code><var>Q</var></code> e restituiti all'utente. <code>dist_between(<var>u</var>, <var>v</var>)</code> calcola la distanza tra due nodi vicini <code><var>u</var></code> e <code><var>v</var></code>. La variabile <code><var>alt</var></code> nelle linee 20 22 rappresenta la lunghezza del percorso dal nodo iniziale al nodo vicino <code><var>v</var></code> se passa da <code><var>u</var></code>. Se questo percorso è più corto dell'ultimo percorso registrato per <code><var>v</var></code>, allora il percorso corrente è rimpiazzato dal percorso identificato con <code><var>alt</var></code>. L'array <code>precedente</code> è popolato con un puntatore al nodo successivo del grafo sorgente per ricevere il percorso più breve dalla sorgente.

1 '''function''' Dijkstra(''Grafo'', ''sorgente''):

2 '''For each''' vertice ''v'' in ''Grafo'': ''// Inizializzazione''

3 dist[''v''] := infinito ; ''// Distanza iniziale sconosciuta''

4 ''// dalla sorgente a v''

5 precedente[''v''] := non definita ; ''// Nodo precedente in un percorso ottimale

6 '''end for''' ''// dalla sorgente''

7

8 dist[''sorgente''] := 0 ; ''// Distanza dalla sorgente alla sorgente''

9 ''Q'' := L'insieme di tutti i nodi nel ''Grafo'' ; ''// Tutti i nodi nel grafo sono''

10 ''// Non ottimizzati e quindi stanno in Q''

11 '''while''' ''Q'' '''non è''' vuota: ''// Loop principale''

12 ''u'' := vertice in ''Q'' con la più breve distanza in dist[] ; ''// Nodo iniziale per il primo caso''

13 rimuovi ''u'' da ''Q'' ;

14 '''if''' dist[''u''] = infinito:

15 '''break''' ; ''// tutti i vertici rimanenti sono''

16 '''end if''' ''// inaccessibili dal nodo sorgente''

17

18 '''For each''' neighbour ''v'' di ''u'': ''// dove v non è ancora stato''

19 ''// rimosso da Q.''

20 ''alt'' := dist[''u''] + dist_tra(''u'', ''v'') ;

21 '''if''' ''alt'' < dist[''v'']: ''// Rilascia (u,v,a)''

22 dist[''v''] := ''alt'' ;

23 precedente[''v''] := ''u'' ;

24 decrease-key ''v'' in ''Q''; ''// Riordina v nella coda''

25 '''end if'''

26 '''end for'''

27 '''end while'''

28 '''return''' dist;

Se siamo interessati solo al percorso minimo tra due vertici <code><var>sorgente</var></code> e <code><var>destinazione</var></code>, possiamo terminare la ricerca alla riga 13 se <code><var>u</var> = <var>destinazione</var></code>.

Adesso possiamo leggere il percorso più breve da <code><var>sorgente</var></code> a <code><var>destinazione</var></code> tramite un'iterazione inversa:

1 ''S'' := sequenza vuota

2 ''u'' := ''destinazione''

3 '''while''' precedente[''u''] è definito: ''// Costruisci il cammino minimo con uno stack S

4 inserisci ''u'' all'inizio di ''S'' ''// Esegui il push del vertice sullo stack

5 ''u'' := precedente[''u''] ''// Traverse da destinazione a sorgente.

6 '''end while''' ;

Adesso la sequenza <code><var>S</var></code> è la lista dei vertici che costituiscono un cammino minimo da <code><var>sorgente</var></code> a <code><var>destinazione</var></code>, o la sequenza vuota se non ci sono percorsi minimi esistenti.

== Tempo di esecuzione ==