L’algoritmo di Dijkstra (1959) risolve il problema della ricerca del cammino minimo in un grafo orientato pesato.

Dato un nodo iniziale x l’algortimo permette di calcolare i cammini minimi verso tutti gli altri nodi del grafo; per trovare i cammini minimi l’algoritmo visita i nodi del grafo provando i possibili cammini.

In ogni istante l’insieme dei nodi del grafo è diviso in tre parti: l’insieme V dei nodi visitati, l’insieme F dei nodi di frontiera, cioè dei nodi che sono successori dei nodi visitati (cioè che si possono raggiungere con un solo arco), e l’insieme dei nodi ancora da visitare.

Per ogni nodo i si tiene traccia della distanza minima d_i calcolata fino a quel momento dal nodo di partenza (inizialmente posta a infinito) e di un nodo p_i (inizialmente indefinito) che rappresenta il nodo precedente da attraversare lungo il cammino reputato minimo fino a i.

Inizialmente V è vuoto, F è costituito dal nodo di partenza x e la sua distanza minima d_x è 0.

L’algoritmo procede prendendo tra i nodi non ancora visitati il nodo j che ha la distanza più piccola dal nodo di partenza, spostandolo tra i nodi visitati e considerando l’insieme dei nodi di frontiera per tale nodo; per tutti i nodi w di frontiera si ricalcola la distanza minima d_w dalla sorgente, prendendo il minimo tra la distanza d_w reputata minima fino a quel momento e la somma tra la distanza fino al nodo appena spostato tra i nodi visitati (d_j) e il peso dell’arco seguito per arrivare al nodo di frontiera w; se la distanza viene modificata p_w viene posto uguale all’ultimo nodo attraversato j.

L’algoritmo prosegue finché l’insieme di frontiera resta vuoto; a questo punto ogni valore d_i rappresenta il peso del cammino minimo da x a i e i valori p permettono di ricostruire l’albero dei cammini minimi con origine in x.

Tutti i nodi del grafo vengono numerati da 1 a n.

La rappresentazione del grafo è costituita da una matrice di adiacenza G, cioè una matrice in cui in ogni elemento (i, j) è contenuto il peso dell’arco che va da i a j.

Dati:

• x valore di input che rappresenta il nodo iniziale;

• n numero dei nodi;

• G(n,n) peso dell’arco da i a j; per gli archi non esistenti valore -1;

• V(n) vettore booleano che indica se un nodo è stato visitato;

• D(n) vettore dei pesi delle distanze minime da ogni nodo alla sorgente x;

• P(n) vettore dei nodi precedenti lungo il cammino minimo da i a x.

per i da 1 a n
   d(i) = infinito
   v(i) = falso
   p(i) = 0
fine per
d(x) = 0
ripeti
   m = infinito
   // trova il nodo che ha distanza minima da x tra quelli non ancora visitati
   per i da 1 a n
      se v(i) = falso
         se d(i) <=m allora
            m = d(i)
            j = i
         fine se
      fine se
   fine per
   se m non è infinito      //se ci sono ancora nodi da visitare
      v(j) = vero        //marca il nodo come visitato
      // esamina i nodi di frontiera per j
      per i da 1 a n
         se g(i, j) > 0      //se esiste l’arco, cioè i è un successore di j
            se d(i) > d(j) + G(i, j)
               d(i) = d(j) + G(i, j)
               p(i) = j
            fine se
         fine se
      fine per
   fine se
finché m = infinito       //tutti i nodi sono stati visitati

Al termine il vettore D contiene il peso dei cammini minimi per ogni destinazione.

Il vettore P permette di ricostruire il cammino da x a ogni nodo.

Il cammino inverso da un nodo i a x si ottiene con:

j = i
ripeti
   stampa p(j)
   j = p(j)
finché j = x