Programmi C/C++ - prof.Claudio Maccherani

Programmi C / C++ - prof. Claudio Maccherani - Perugia - 2008
Algoritmo di Dijkstra
soluzione in C++ proposta dalla prof.ssa Paola Masin

 /* Algoritmo di DIJKSTRA: ricerca cammino minimo su grafo orientato
    in input sulla prima riga: numero nodi, nodo iniziale, nodo finale
    nelle righe successive gli archi (terne di: nodo, nodo, peso)
    si suppongono i nodi numerati a partire da zero.
    'maquillage' di Claudio Maccherani, del 2008, di un programma di 
    Paola Masin del 18/12/2006

    +-----------+      +--------------------------+
    | input.txt |      |       output.txt         |
    +-----------+      +--------------------------+
    |  6  1  5  |      | cammino di peso 6        |
    |  0  1  3  |      | percorso a ritroso 5 4 1 |
    |  0  5  2  |      +--------------------------+
    |  1  2  5  |
    |  2  3  1  |
    |  3  4  3  |
    |  4  5  2  |
    |  5  1  6  |
    |  1  4  4  |
    +-----------+ */

 #include <fstream>
 #include <limits.h>

 using  namespace std;

 int main() { 
   // variabili di servizio, dimensionamento, inizializzazione
   int i,j,k, Inizio, Fine, Min, Attuale;
   ifstream in("input.txt");    // file di input
   int n;                       // numero nodi
   in>>n;                       // lettura numero nodi
   int G[n][n];                 // MATRICE di ADIACENZE
   in>>Inizio;                  // nodo di partenza
   in>>Fine;                    // nodo di arrivo
   // inizializza matrice adiacenze: se non c'è l'arco, l'elemento vale INT_MAX
   for (i=0; i<n; i++) 
       for (j=0; j<n; j++) G[i][j] = INT_MAX;
   // lettura dal file dei pesi degli archi del grafo e inserimento in matrice
   while (!in.eof()) { in>>i; in>>j; in>>G[i][j]; }
   in.close();
   // definizione strutture per l'algoritmo
   int D[n]; // vettore delle DISTANZE che contiene, per ciascun nodo,
             // la distanza minima dal nodo iniziale
             // serve anche come insieme dei nodi di frontiera
             // (nodi raggiungibili da qualcuno dei precedentemente esaminati)
   for (i=0; i<n; i++) D[i] = INT_MAX;
             // se  D[i] == INT_MAX il nodo non risulta ancora adiacente 
             // a nessuno dei nodi visitati, quindi non é in frontiera
   int P[n]; // vettore delle PROVENIENZE che contiene, per ciascun nodo,
             // il nodo che lo precede nel cammino minimo
   for (i=0; i<n; i++)  P[i] = -1; // -1 provenienza sconosciuta
   int V[n]; // vettore dei VISITATI che contiene, per ciascun nodo,
             // 0 se il nodo non è stato visitato, 1 altrimenti
   for (i=0; i<n; i++)  V[i] = 0;
   D[Inizio] = 0; // Inizio è il nodo di partenza, la sua distanza da sé é 0
   Attuale = Inizio;
   Min = 0;       // distanza minima dal nodo attuale
   while ( Attuale!=Fine && Min!=INT_MAX) {
      // si cerca il nodo più promettente, ossia quello con distanza minima
      // che non sia ancora stato visitato
      Min = INT_MAX;
      for (i=0; i<n; i++)
         if ( V[i] == 0 && D[i] < Min ){ Min = D[i]; Attuale = i; }
         V[Attuale] = 1; //Attuale è il nodo scelto che poi non si elaborerà più
         // aggiornamento vettori distanze (D) e provenienze (P)
         for (i=0; i<n; i++)
            if ( G[Attuale][i] != INT_MAX && D[i] > D[Attuale] + G[Attuale][i])
               { D[i] = D[Attuale] + G[Attuale][i]; P[i] = Attuale; }
      } //while
   ofstream out("output.txt");  // file di output
   if ( V[Fine] == 0)
      out<<"NON esiste cammino da nodo "<<Inizio<<" a "<<Fine;
   else { out<<"cammino di peso "<<D[Fine];
          i=Fine;
          out<<"\npercorso a ritroso ";
          while (i!=Inizio) { out<<i<<" "; i=P[i]; }
          out<<i<<" "; }
   out.close();
   return 0; }