Algoritmo di Dijkstra: differenze tra le versioni

Versione delle 06:24, 29 ago 2006

Versione delle 23:50, 18 set 2006

Riga 1:

{{vetrina inserimento}}

L<nowiki>'</nowiki>'''algoritmo di Dijkstra''' deve il suo nome all'informatico [[Edsger Dijkstra]] e permette di trovare i [[cammino minimo|cammini minimi]] (o Shortest Paths, SP) in un [[grafo]] ciclico orientato con pesi non negativi sugli archi: in particolare l'algoritmo può essere utilizzato parzialmente per trovare il cammino minimo che unisce due nodi del grafo, totalmente per trovare quelli che uniscono un nodo d'origine a tutti gli altri nodi o più volte per trovare tutti i cammini minimi da ogni nodo ad ogni altro nodo. Tale algoritmo trova applicazione in molteplici contesti. Per esempio permette, dato un grafo che rappresenta un'ipotetica "mappa" di condotte di approvvigionamento idrico di una città, di calcolare qual è il cammino minimo, e quindi ottimizzare la realizzazione della rete idrica. Esempio analogo può essere fatto considerando il "problema" di trovare il collegamento meno dispendioso, in termini di potenza dissipata, nella realizzazione di un circuito elettrico.

Nell'applicare tale algoritmo ai vari campi dello scibile umano, e' sicuramente utile affidarsi ad un calcolatore opportunamente istruito con l'algoritmo stesso.