Algoritmo di Dijkstra: differenze tra le versioni

Versione delle 17:16, 26 apr 2019

Versione delle 10:23, 30 apr 2019

Riga 86:

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 sequito 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|heap di Fibonacci]].

{| class="wikitable"

Riga 98:

| <math>\Theta(|V|)</math> || <math>O(\log_2 |V|)</math> || <math>O(\log_2 |V|)</math> || <math>O((|V|+|E|) \log_2 |V|)</math>

|-

! [[Heap di Fibonacci|Heap di Fibonacci]]

| <math>\Theta(|V|)</math> || <math>O(\log_2 |V|)</math><ref name="ammortizata">Analisi ammortizzata</ref> || <math>\Theta(1)</math><ref name="ammortizata"/> || <math>O(|V|\log_2 |V| + |E|)</math><ref name="ammortizata">Analisi ammortizzata</ref>

|}