Algoritmo dijkstra

Supponiamo di assegnare a ciascuno degli archi a di un grafo orientato G un certo peso intero e positivo pa. Ai cammini (orientati) nel grafo (cioè sequenze di archi consecutivi) verrà a questo punto assegnato un peso, dato dalla somma dei pesi degli archi che lo compongono. Dati due nodi x e y, il problema del cammino minimo consiste nel fornire un cammino da x a y di peso minimo. Se tutti gli archi sono pesati 1 (cioè pa D 1 per ogni arco a) il problema si riduce a quello delle distanze minime, facilmente risolubile con una visita in ampiezza. Se però ci sono pesi diversi da 1, è facile rendersi conto che una visita in ampiezza non è sufficiente. Ad esempio, se nel grafo seguente vogliamo sapere qual è un cammino minimo dal nodo 0 al nodo 5. una visita in ampiezza a partire dal nodo 0 assegnerebbe immediatamente al nodo 4 un cammino minimo di peso 6, e (nel caso migliore) al passo successivo un cammino di peso 4 (attraverso il nodo 1), ma, inevitabilmente, al momento di visitare il nodo 4 assegneremmo al nodo 5 un cammino di peso 5, mentre “aspettando un po’” se ne sarebbe potuto trovare uno di peso inferiore passante per il nodo 1 e il nodo 3. Per evitare fenomeni di questo tipo, è necessario visitare per primi i nodi che hanno cammini minimi da 0 più brevi. Edsger W. Dijkstra ha proposto nel 1959 [1] un algoritmo molto elegante che risolve questo problema. Vediamo innanzitutto come funziona l’algoritmo in astratto—forniremo poi diverse implementazioni con diversi compromessi tra efficienza, generalità e semplicità. L’algoritmo di Dijkstra visita i nodi nel grafo, in maniera simile a una ricerca in ampiezza o in profondità. In ogni istante, l’insieme N dei nodi del grafo è diviso in tre parti: l’insieme dei nodi visitati V, l’insieme dei nodi di frontiera F, che sono successori1 dei nodi visitati, e i nodi sconosciuti, che sono ancora da esaminare. Per ogni nodo z, l’algoritmo tiene traccia di un valore dz , inizialmente posto uguale a 1, e di un nodo uz , inizialmente indefinito. Continua »