Algoritmo di Dijkstra: differenze tra le versioni

Versione delle 23:08, 28 gen 2018

Versione attuale delle 17:42, 14 dic 2023

(41 versioni intermedie di 35 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]]}}

{{Avvisounicode}}

{{nota disambigua|l'algoritmo per la [[mutua esclusione]] in sistemi concorrenti, detto anche "algoritmo di proiezione di Dijkstra"|la voce [[algoritmo 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 =

Line 13 ⟶ 12:

|completo =

}}

L<nowiki>{{'</nowiki>}}'''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 realizzazionirealizzazione di reti (idriche, [[telecomunicazioni]], stradali, circuitali, ecc.) o l'organizzazione e la valutazione di percorsi runtime nel campo della [[robotica]].

Lo stesso Edsger amava riassumere con 'La sega non è valida se non è fatta con la sinistra'.

Tale algoritmo trova applicazione in molteplici contesti quale l'ottimizzazione nella realizzazioni 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 1uno siadi sceltoquesti comenodi nodosia 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)''. AdA 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''.

Line 36 ⟶ 34:

==Pseudocodice==

Nel seguente algoritmo, il codice <code>u := vertici in ''Q'' con la più breve dist[]</code>, cerca per dei verticinodi <code><var>u</var></code> nell'insieme dei verticinodi <code><var>Q</var></code> che hanno il valore <code>dist[<var>u</var>]</code> più piccolo. Questi verticinodi sono rimossi dall'insieme <code><var>Q</var></code> e restituiti all'utente. <code>dist_betweendist_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''):

Line 42 ⟶ 40:

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

Line 54 ⟶ 52:

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

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

17

18 '''For each''' neighbour ''v'' di ''u'': ''// dove v non è ancora stato''

19 ''// rimosso da Q.''

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

21 '''if''' ''alt'' < dist[''v'']: ''// Rilasciaquesta condizione e' sempre false se (u,v,a) e' gia stato rimosso da Q''

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

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

Line 67 ⟶ 64:

28 '''return''' dist;

Se siamo interessati solo al percorso minimo tra due verticinodi <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 verticinodi 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

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

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

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

Line 110 ⟶ 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:

Line 125 ⟶ 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 utilizzati da nessun cammino.

Line 144 ⟶ 151:

== Altri progetti ==

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

{{Algoritmi ricerca grafi}}

{{Portale|informatica|matematica}}

[[Categoria:Algoritmi di ottimizzazione|Dijkstra]]