Algoritmo di Dijkstra: differenze tra le versioni

Versione delle 18:25, 12 nov 2023

Versione attuale delle 17:42, 14 dic 2023

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