Ciao ragazzi, sto cercando di risolvere un esercizio:
"Dati un vertice sorgente, uno destinazione e una tipologia di distanze (d1 oppure d2 oppure
d3) inseriti dall’utente, calcola il percorso più breve tra sorgente e destinazione, mostrando a
monitor tale percorso e la relativa distanza."
Essendo che la struttura dati in questione è un grafo orientato e che d1 d2 e d3 sono i pesi del grafo (numeri reali tipo 1.2, 3.4, 5.6 etc, tutti positivi) pensavo di utilizzare l'algoritmo di Dijkstra,
è la soluzione migliore per il mio caso? Ho a disposizione lo pseudocodice da alcune dispense, ma ho bisogno di
aiuto per implementarlo in C.
Ci sono due cose che non mi sono chiare:
1) questa riga nella funzione 'inizializza':
vertice_p->distanza_min = INFINITO;
come implemento questo INFINITO?
2) /costruisci un insieme per i vertici già considerati (inizialmente vuoto) .;
/costruisci una struttura per i vertici da considerare (inizialmente tutti) .;
non sono sicuro di aver capito come svolgere questa parte.
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);
}
}
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;
}
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;
}
}
Spero in qualche risposta visto che nel thread che ho creato qualche settimana fa non rispose nessuno.