|
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 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 1 sia scelto come nodo di partenza. Il peso sull'arco che congiunge i nodi j e k è indicato con ''p(j,k)''. Ad 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 T=T<math>\setminus</math>{j} e S=S∪{j}
#* 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==
| 