Salve ragazzi. Avrei bisogno di aiuto con il seguente esercizio:
Praticamente devo calcolare il percorso breve tra un vertice sorgente e un vertice destinazione (inseriti entrambi da tastiera). I vertici in questione ovviamente fanno parte di un grafo, e questo grafo è pesato.
Pensavo di risolvere la cosa utilizzando l'algoritmo di Dijkstra, dalle dispense che ho a disposizione:
codice:
void dijkstra(vertice grafo t *grafo p,
vertice grafo t *sorgente p)
{
vertice grafo t *vertice p;
arco grafo t *arco p;
inizializza(grafo p,
sorgente p);
/*costruisci un insieme per i vertici già considerati (inizialmente vuoto) ;*/
/*costruisci una struttura per i vertici da considerare (inizialmente tutti);*/
while (la struttura non è vuota )
{
/*rimuovi dalla struttura il vertice vertice p con distanza min minima;*/
/*inserisci vertice p nell'insieme dei vertici già considerati;*/
for (arco p = vertice p->lista archi p;
(arco p != NULL);
arco p = arco p->arco succ p)
if (/*arco p->vertice adiac p non è nell'insieme dei vertici già considerati*/)
riduci(arco p,
vertice p);
}
}
codice:
void inizializza(vertice_grafo_t *grafo_p,
vertice_grafo_t *sorgente_p)
{
vertice_grafo_t *vertice_p;
for (vertice_p = grafo_p;
(vertice_p != NULL);
vertice_p = vertice_p->vertice_succ_p)
{
vertice_p->distanza_min = INFINITO;
vertice_p->padre_p = NULL;
}
sorgente_p->distanza_min = 0.0;
}
codice:
void riduci(arco_grafo_t *arco_p,
vertice_grafo_t *vertice_p) /* vertice da cui l’arco esce */
{
if (arco_p->vertice_adiac_p->distanza_min > vertice_p->distanza_min + arco_p->peso)
{
arco_p->vertice_adiac_p->distanza_min = vertice_p->distanza_min + arco_p->peso;
arco_p->vertice_adiac_p->padre_p = vertice_p;
}
}
Non so bene come svolgere questa parte:
/*costruisci un insieme per i vertici già considerati (inizialmente vuoto) ;*/
/*costruisci una struttura per i vertici da considerare (inizialmente tutti);*/
Qualcuno può aiutarmi?
Perdonate la mia scarsezza in programmazione, è solo il 3° esercizio che svolgo.