Algoritmo di Dijkstra
L'algoritmo di Dijkstra deve il suo nome all'informatico Edsger Dijkstra e permette di trovare i 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 in passi
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 riporta il nodo sul cammino minimo che porta al nodo i-esimo subito precedente questo ultimo. 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-{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
- Per ogni i in T, adiacente a j e tale che f(i)>f(j)+p(j,i) poniamo: