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:
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é |
||||||||||