Olimpiadi di Informatica
Algoritmo di Dijkstra
soluzione in C++ proposta dalla prof.ssa Paola Masin

 

Algoritmo di Dijkstra

 

Un tipico problema, quando si ha a che fare con grafi che ad esempio rappresentano mappe, è quello della determinazione del cammino di lunghezza minima tra due nodi (il percorso minimo tra due punti della mappa).

Se il grafo non è orientato il problema sui riduce a quello delle distanze minime, risolubile con una visita in ampiezza (BFS - Breadth First Search).

Uno strumento efficiente per affrontare il problema, sia con grafi orientati che no (in questo caso si assegna valore 1 a ciascun arco del grafo), è l’algoritmo proposto da Edsger W.Dijstra nel 1959.

 

Si visitano i nodi del grafo in maniera simile a una visita in ampiezza o in profondità.

L’insieme dei nodi N del grafo è suddiviso in  tre parti:

- insieme dei nodi visitati V

- insieme dei nodi di frontiera F, successori dei nodi visitati

- insieme dei nodi sconosciuti, ancora da esaminare

Una implementazione dell’algoritmo, proposta dalla prof.ssa Paola Masin (referente regionale per il Veneto - VEN2 - delle Olimpiadi di Informatica), utilizza le seguenti strutture dati:

matrice delle adiacenze G con i nodi indicati da un numero intero da 0 a n.

vettore delle distanze D che contiene, per ciascun nodo, la distanza minima dal nodo iniziale. Tale vettore serve anche per i nodi di frontiera (cioè i nodi raggiungibili da qualche nodo precedentemente esaminato). Viene inizializzato a infinito (), INT_MAX in C++, per indicare che il nodo non risulta ancora adiacente a nessuno dei nodi visitati, non è stato raggiunto da alcun percorso ed è quindi di frontiera.

vettore delle provenienze P che contiene, per ciascun nodo, il numero del nodo che lo precede nel cammino minimo. Viene inizializzato a –1, per indicare provenienza sconosciuta.

vettore dei nodi visitati V che contiene, per ciascun nodo, 0 se non visitato, 1 se visitato. Inizializzato a 0.

Attuale è il nodo in esame, Inizio è il nodo iniziale, Fine è il nodo finale, Min di appoggio.

 Algoritmo

la distanza di Inizio e Min valgono 0 

il nodo Attuale è il nodo Inizio

il nodo Attuale è visitato

finché   nodo Attuale è diverso da nodo Fine  e  ci sono ho ancora nodi  ai quali arrivare

           per ogni nodo i

aggiorna le distanze, sostituendo, se è vantaggiosa, la distanza che si ottiene arrivando dal nodo Attuale + il collegamento con i ( se esiste ) e in tal caso si aggiorna anche la provenienza

si cerca il nodo più promettente, ossia quello che ha attualmente distanza minima che non sia ancora stato visitato, che diventa nodo Attuale. Se non ho più nodi raggiungibili la distanza minima è infinito.

         Il nodo Attuale è il nodo scelto e poi non sarà più elaborato, quindi si pone a visitato

torna al finché