Algoritmo di Dijkstra: differenze tra le versioni

Versione delle 12:05, 12 dic 2018

Versione delle 12:13, 15 apr 2019

Riga 79:

== Tempo di esecuzione ==

IlLa tempocomplessità di esecuzionecomputazionale dell'algoritmo di Dijkstra può essere espressoespressa in funzione di <math>|V|</math> ed <math>|E|</math> ossia, rispettivamente, il numero di vertici e degli archi appartenenti al grafo sul quale viene eseguito. L'algoritmo utilizza una coda di priorità, implementatasu attraversocui unvengono Min-Heapeffettuate tre operazioni: la costruzione della coda, Max-Heapl'estrazione odell'elemento minimo e la riduzione del valore di un alberoelemento. Red-BlackLa 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

In questo caso dunque il tempo di esecuzione può essere espresso nella forma:

<math>OT_D(G) = \biglTheta(|EV|) + T_B(|V|) + |V| * T_E(|V|) + |E| * T_U(|V^2|\bigr)</math>

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.

Assumendo che il grafo sia generico vale l'approssimazione <math>|E| = O(|V^2|)</math> e dunque il tempo di esecuzione può essere riscritto come:

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]].

<math>O\bigl(|E|+|V^2|\bigr) = O\bigl(|V^2|\bigr)</math>

{| class="wikitable"

Possiamo quindi concludere affermando che il tempo di esecuzione dell'algoritmo di Dijkstra è proporzionale al quadrato del numero dei vertici appartenenti al grafo sul quale viene eseguito.

|+ Complessità dell'algoritmo di Dijkstra in funzione dell'implementazione la coda di priorità

! !! Costruire la coda !! Estrarre il minimo !! Ridurre un valore !! Algoritmo di Dijkstra

|-

! Arrays

| <math>\Theta(|V|)</math> || <math>O(|V|)</math> || <math>\Theta(1)</math> || <math>O(|V|^2+|E|)</math>

|-

! [[Heap binario|Heap binarie]]

| <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>

|}

{{reflist}}

È 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 ==