Come faccio a implementare Dijkstra su un grafo implementato in questo modo:
struct elemento_grafo// struttura degli elementi del grafo
{ string nome_citta;
int num_collegamenti;
vector <collegamento> adiacenti; // lista di adiacenti
elemento_grafo* precedente; //puntatore a elemento precedente
float minimo;}; //stima del cammino minimo dalla sorgente
class grafo // -----------------------------------------------------------------
{ private:
vector <elemento_grafo> mappa;
public:
....
void inizializza_min_prec (string c) // inizializza precedente e minimo con sorgente c
{ int n=mappa.size();
for (int i=0; i<n; i++)
{ mappa.at(i).precedente = NULL;
mappa.at(i).minimo = 999999;
if (mappa.at(i).nome_citta == c)
mappa.at(i).minimo = 0;
}
return ; }
void rilassa (elemento_grafo* u, elemento_grafo* v, float pesou)
{ if ( v->minimo > (u->minimo+pesou) )
{ v->minimo = u->minimo + pesou;
v->precedente = u;}
return;
}
elemento_grafo* estrai_piccolo ()
{ int n=mappa.size();
int posizione_min=0;
elemento_grafo* min = &(mappa.at(0)); //& ritorna l'indirizzo (puntatore)
elemento_grafo* punt;
for (int i=1; i<n; i++)
{ punt = &(mappa.at(i));
if ( punt->minimo < min->minimo)
{ min = punt;
posizione_min = i; }
}
mappa.erase(mappa.begin()+posizione_min);
return min;
}
void dijkstra (string sorgente)
{ inizializza_min_prec (sorgente);
}