Algoritmo di Dijkstra: differenze tra le versioni

Versione delle 07:58, 12 apr 2023

Versione attuale delle 10:59, 24 lug 2025

(4 versioni intermedie di 4 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 25:

#* 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>T = T \setminus \{j\}</math>{j} e <math>S =S∪ S \cup \{j\}</math>;

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

# ''Assegnazione etichetta provvisoria''

Riga 55:

18 '''For each''' neighbour ''v'' di ''u'':

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

21 '''if''' ''alt'' < dist[''v'']: ''// questa condizione e' sempre false se v e'è giagià stato rimosso da Q''

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

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

Riga 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