Algoritmo di Dijkstra: differenze tra le versioni

Versione delle 13:25, 9 gen 2018

Versione attuale delle 10:59, 24 lug 2025

(46 versioni intermedie di 40 utenti non mostrate)

Riga 1:

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

{{Avvisounicode}}

{{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|titolo=Fibonacci Heaps And Their Uses In Improved Network Optimization Algorithms}}</ref>

|tempo migliore =

|tempo medio =

|spazio =

|ottimale =

|completo =

}}

L{{'}}'''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]].

== Algoritmo ==

Supponiamo di avere un grafo con n vertici contraddistinti da numeri interi {1,2,...,n} e che uno di questi nodi sia quello di partenza e un altro quello di destinazione. Il peso sull'arco che congiunge i nodi j e k è indicato con ''p(j,k)''. A ogni nodo, al termine dell'analisi, devono essere associate due etichette, ''f(i)'' che indica il peso totale del cammino (la somma dei pesi sugli archi percorsi per arrivare al nodo i-esimo) e ''J(i)'' che indica il nodo che precede i nel cammino minimo. Inoltre definiamo due insiemi ''S'' e ''T'' che contengono rispettivamente i nodi a cui sono già state assegnate le etichette e quelli ancora da scandire.

# ''Inizializzazione''.

#* Poniamo ''S''={1}, ''T''={2,3,...,n}, f(1)=0, J(1)=0.

#* Poniamo f(i)=p(1,i), J(i)=1 per tutti i nodi adiacenti ad 1.

#* Poniamo f(i)= ∞, per tutti gli altri nodi.

# ''Assegnazione etichetta permanente''

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

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

# ''Assegnazione etichetta provvisoria''

#* Per ogni i in T, adiacente a j e tale che f(i)>f(j)+p(j,i) poniamo:

#** f(i)=f(j)+p(j,i)

#** J(i)=j

#* Andiamo al passo 2

==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_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''):

2 '''For each''' vertice ''v'' in ''Grafo'': ''// Inizializzazione''

3 dist[''v''] := infinito ; ''// Distanza iniziale sconosciuta''

4 ''// dalla sorgente a v''

5 precedente[''v''] := non definita ; ''// Nodo precedente in un percorso ottimale''

6 '''end for''' ''// dalla sorgente''

7

8 dist[''sorgente''] := 0 ; ''// Distanza dalla sorgente alla sorgente''

9 ''Q'' := L'insieme di tutti i nodi nel ''Grafo'' ; ''// Tutti i nodi nel grafo sono''

10 ''// Non ottimizzati e quindi stanno in Q''

11 '''while''' ''Q'' '''non è''' vuota: ''// Loop principale''

12 ''u'' := vertice in ''Q'' con la più breve distanza in dist[] ; ''// Nodo iniziale per il primo caso''

13 rimuovi ''u'' da ''Q'' ;

14 '''if''' dist[''u''] = infinito:

15 '''break''' ; ''// tutti i vertici rimanenti sono''

16 '''end if''' ''// inaccessibili dal nodo sorgente''

17

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 è già stato rimosso da Q''

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

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

24 decrease-key ''v'' in ''Q''; ''// Riordina v nella coda''

25 '''end if'''

26 '''end for'''

27 '''end while'''

28 '''return''' dist;

Se siamo interessati solo al percorso minimo tra due nodi <code><var>sorgente</var></code> e <code><var>destinazione</var></code>, possiamo terminare la ricerca alla riga 13 se <code><var>u</var> = <var>destinazione</var></code>.

Adesso possiamo leggere il percorso più breve da <code><var>sorgente</var></code> a <code><var>destinazione</var></code> tramite un'iterazione inversa:

1 ''S'' := sequenza vuota

2 ''u'' := ''destinazione''

3 '''while''' precedente[''u''] è definito: ''// Costruisci il cammino minimo con uno stack S''

4 inserisci ''u'' all'inizio di ''S'' ''// Esegui il push del vertice sullo stack''

5 ''u'' := precedente[''u''] ''// Traverse da destinazione a sorgente.''

6 '''end while''' ;

Adesso la sequenza <code><var>S</var></code> è la lista dei nodi che costituiscono un cammino minimo da <code><var>sorgente</var></code> a <code><var>destinazione</var></code>, o la sequenza vuota se non ci sono percorsi minimi esistenti.

== Tempo di esecuzione ==

IlLa tempo[[Teoria didella complessità computazionale|complessità esecuzionecomputazionale]] dell'algoritmo di Dijkstra può essere espressoespressa in funzione di <math>|V|</math> eed <math>|E|</math> ossia, rispettivamente, il numero di verticinodi 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

:<math>T_D(G) = \Theta(|V|) + T_B(|V|) + |V| * T_E(|V|) + |E| * T_U(|V|)</math>

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

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.

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

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

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:

{| class="wikitable"

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

|+Complessità dell'algoritmo di Dijkstra in funzione dell'implementazione della 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]]

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

|}

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

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.

== Esempio ==

Alla base di questi problemi c'è lo scopo di trovare il percorso minimo (più corto, più veloce, più economico…) tra due punti, uno di partenza e uno di arrivo. Con il metodo che si vedrà è possibile ottenere non solo il percorso minimo tra un punto di partenza e uno di arrivo ma l'[[albero dei cammini minimi]], cioè tutti i percorsi minimi tra un punto di partenza e tutti gli altri punti della rete. Come per praticamente tutti i problemi riguardanti le reti la cosa migliore è fare una schematizzazione della situazione per risolvere l'esercizio più agevolmente e avere sempre a disposizione i dati necessari. Una buona schematizzazione per i problemi di percorso minimo deve includere tutti i possibili collegamenti tra i nodi (e i relativi costi) e deve essere fissato un nodo di partenza.

Con il metodo che vedremo è possibile ottenere non solo il percorso minimo tra un punto di partenza e uno di arrivo ma l'[[albero dei cammini minimi]], cioè tutti i percorsi minimi tra un punto di partenza e tutti gli altri punti della rete.

Come per praticamente tutti i problemi riguardanti le reti la cosa migliore è fare una schematizzazione della situazione in cui ci troviamo per risolvere l'esercizio più agevolmente ed avere sempre a disposizione i dati necessari.

Una buona schematizzazione per i problemi di percorso minimo deve includere tutti i possibili collegamenti tra i nodi (ed i relativi costi) e deve essere fissato un nodo di partenza.

ConsideriamoSi consideri un problema in cui si vuole calcolare il percorso minimo tra casa e il posto di lavoro. SchematizziamoSi schematizzino tutti i possibili percorsi ede il relativo tempo di percorrenza (supponendo di voler calcolare il percorso più breve in fatto di tempo di percorrenza). I nodi A, B, C, D, E indicano le cittadine per cui è possibile passare. Ecco una schematizzazione della rete:

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

DobbiamoBisogna ora assegnare ada ogni nodo un valore, che chiameremochiamato “potenziale”, seguendo alcune regole:

<div style="float:center; width:80%; padding:15px; background: #f5f8ff; border: 1px solid blue; margin-left:8px; margin-right:8px;margin-bottom:15px; text-align:left">

* Ogni nodo ha, all'inizio potenziale <math>+ \infty</math> (che indichiamo con “inf”);

* Il nodo di partenza (in questo caso “casa”) ha potenziale 0 (ovvero dista zero da sesé stesso);

* Ogni volta si sceglie il nodo con potenziale minore e lo si rende definitivo (colorando il potenziale di rosso) e si aggiornano i nodi adiacenti;

* Il potenziale di un nodo è dato dalla somma del potenziale del nodo precedente + il costo del collegamento;

Riga 33 ⟶ 118:

* Quando si aggiorna il potenziale di un nodo si lascia quello minore (essendo un problema di percorso minimo).

</div>

VediamoSi in praticaveda come si risolve questo esercizio nella pratica. Questa è la rete in cui sono indicati anche i potenziali:

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

Seguendo le regole appena fissate consideriamosi consideri il nodo con potenziale minore (“casa”) e lo rendiamosi renda definitivo (colorandolo di rosso) ede si aggiorniamoaggiornino tutti i nodi adiacenti sommando l'attuale valore del potenziale (ovvero zero) al costo del percorso. AggiorniamoSi aggiornino i potenziali perché avevamosi aveva, nel caso di A, potenziale infinito mentre ora abbiamoil potenziale è 2. Ricordando che il potenziale minore è sempre preferibile. VediamoEcco come si è aggiornata la rete:

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

Bisogna ora considerare il nodo non definitivo (ovvero quelli scritti in nero) con potenziale minore (il nodo A). Lo si rende definitivo e si aggiornano i potenziali dei nodi adiacenti B e C. IndichiamoSi indichi con una freccia da dove proviene il potenziale dei nodi resi definitivi.

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

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 avessimosi avutofosse ottenuto un valore maggiore di quello che già c'era losi avremmosarebbe lasciatodovuto lasciare invariato. Si renda definitivo il nodo D e si aggiorni il grafico:

Rendiamo definitivo il nodo D e aggiorniamo 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:

Riga 48 ⟶ 132:

Restano da considerare il nodo E e da aggiornare “ufficio”.

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

Seguendo all'indietro le frecce si ottiene il percorso minimo da casa ada ufficio che misura (come indicato dal potenziale) “10”.

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

Bisogna notare come questo algoritmo ci dia non solo la distanza minima tra il punto di partenza e quello di arrivo ma la distanza minima di tutti i nodi da quello di partenza, da cui si può realizzare l'albero dei cammini minimi semplicemente eliminando gli archi non utilizzati da nessun cammino.

==Note==

Riga 67 ⟶ 151:

== Altri progetti ==

{{interprogetto|commonspreposizione=Dijkstrasull's algorithm}}

{{Algoritmi ricerca grafi}}

{{Portale|informatica|matematica}}

[[Categoria:Algoritmi di ottimizzazione|Dijkstra]]