Algoritmo di Dijkstra: differenze tra le versioni

Versione delle 10:28, 15 dic 2020

Versione attuale delle 17:42, 14 dic 2023

(8 versioni intermedie di 8 utenti non mostrate)

Riga 1:

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

{{Algoritmo

|classe = [[Algoritmo di ricerca]]

|immagine = Dijkstra Animation.gif

|didascalia = Esecuzione dell'algoritmo di Dijkstra

|struttura dati = [[Grafo (tipo di dato astratto)|Grafo]]

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

|tempo migliore =

|tempo medio =

Riga 12:

|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 realizzazione di reti (idriche, [[telecomunicazioni]], stradali, circuitali, ecc.) o l'organizzazione e la valutazione di percorsi runtime nel campo della [[robotica]].

Riga 34:

==Pseudocodice==

Nel seguente algoritmo, il codice <code>u := vertici in ''Q'' con la più breve dist[]</code>, cerca per dei nodi <code><var>u</var></code> nell'insieme dei nodi <code><var>Q</var></code> che hanno il valore <code>dist[<var>u</var>]</code> più piccolo. Questi nodi sono rimossi dall'insieme <code><var>Q</var></code> e restituiti all'utente. <code>dist_betweendist_tra(<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''):

Riga 53:

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'']: ''// Rilasciaquesta condizione e' sempre false se (u,v,a) e' gia stato rimosso da Q''

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

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

Line 78 ⟶ 77:

== Tempo di esecuzione ==

La [[Teoria della complessità computazionale|complessità computazionale]] dell'algoritmo di Dijkstra può essere espressa in funzione di <math>|V|</math> ed <math>|E|</math> ossia, rispettivamente, il numero di nodi e degli archi appartenenti al grafo sul quale viene eseguito. L'algoritmo utilizza una [[coda di priorità]] su cui vengono effettuate tre operazioni: la costruzione della coda, l'estrazione dell'elemento minimo e la riduzione del valore di un elemento. La [[struttura dati]] utilizzata per l'implementazione della coda di priorità determina la complessità di queste tre operazioni e, di conseguenza, quella dell'algoritmo.

In generale, la complessità, <math>T_D(G)</math>, dell'algoritmo di Dijkstra è limitata superiormente da

Line 86 ⟶ 85:

dove <math>T_B(|V|)</math>, <math>T_E(|V|)</math> e <math>T_U(|V|)</math> sono le complessità necessarie alle operazioni di costruzioni di una coda con <math>|V|</math> elementi, estrazione del minimo da una coda con <math>|V|</math> elementi e la riduzione di un valore in una coda con <math>|V|</math> elementi.

Di sequitoseguito sono riportate le complessità di <math>T_B(|V|)</math>, <math>T_E(|V|)</math>, <math>T_U(|V|)</math> e dell'algoritmo di Dijkstra nel caso in cui le code di priorità siano implementate tramite array, [[Heap binario|heap binarie]] o [[heap di Fibonacci]].

{| class="wikitable"

Line 103 ⟶ 102:

È interessante notare che, nel caso in cui il grafo '''non''' sia sufficientemente sparso e <math>|E| \in \Omega( |V|^2 / \log_2 |V| )</math>, la soluzione basata sugli array è più efficiente di quella implementata tramite le [[Heap binario|heap binarie]].

== Esempio ==

Line 128 ⟶ 126:

Il nodo con potenziale minore ora è C. lo si rende definitivo e si aggiornano quelli adiacenti.

[[File:Ricerca operativa percorso minimo 05.gif|center]]

Va notato come il nodo D abbia ora potenziale 6 in quanto 6 è minore di 8 e quindi lo si aggiorna. Se si avessefosse ottenuto un valore maggiore di quello che già c'era si sarebbe dovuto lasciare invariato. Si renda definitivo il nodo D e si aggiorni il grafico:

[[File:Ricerca operativa percorso minimo 06.gif|center]]

Il nodo con potenziale minore restante è B e lo si rende definitivo aggiornando di conseguenza il grafico:

Line 153 ⟶ 151:

== Altri progetti ==

{{interprogetto|preposizione=sull'}}

{{Algoritmi ricerca grafi}}