Algoritmo di Dijkstra: differenze tra le versioni

Versione delle 14:28, 17 mar 2021

Versione delle 03:26, 26 mag 2021

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

Riga 53:

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 e' gia stato rimosso da Q''

Riga 102:

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