Algoritmo di Dijkstra: differenze tra le versioni

Versione delle 12:17, 1 lug 2006

Versione delle 19:49, 1 lug 2006

Riga 1:

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.

==Algoritmo matematico==

Riga 21:

==Risoluzione pratica di un esercizio==

Alla base di questi problemi c’è lo scopo di trovare il percorso minimo (più corto, più veloce, più economico, …economico…) tra due punti, uno di partenza e uno di arrivo.

Con il metodo che vedremo è possibile ottenere non solo il percorso minimo tra un punto di partenza e uno di arrivo ma il percorso minimo 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.

Riga 56:

[[Immagine: 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 nodi da quello di partenza.

[[Categoria:Algoritmi]]