Algoritmo di Dijkstra

L'algoritmo di Dijkstra deve il suo nome all'informatico Edsger Dijkstra e permette di trovare i cammini minimi in un grafo ciclico orientato con pesi positivi 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.

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)=1.
- 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
- 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=∅ o f(i)= ∞ per ogni i in T STOP
Assegnazione etichetta provvisoria
- Per ogni (j,i) in T tale che f(i)>f(j)+p(i,j) poniamo:
  - f(i)=f(j)+p(i,j)
  - J(i)=j
- Andiamo al passo 2