[C/C++]: Valori sovrascritti in lista nodi collegati

[Rik142]

Fastcoder, ho bisogno però di un'altro aiuto.
Dato un struct nodoCollegato *po; e nel momento in cui pongo po = G[0] bisogna che gli passi esattamente G[0].elencoVerticiCollegati giusto?

Un'altra cosa: quindi la soluzione con il vettore mantiene per ogni vertice quali sono i vertici direttamente collegati ad esso oppure li inserisce uno dietro l'altro?

Anche se ormai mi sembra che tu me l'abbia già detto, te lo richiedo perchè dovendo analizzare ogni singolo vertice e scegliendo quello che ha percorso minimo, alla fine lo devo settare in maniera tale da non doverlo più utilizzare. Questa è la logica del programma che sto scrivendo e se tutto funziona com'era in origine, (ossia come sopra descritto), vuol dire che non ho altre modifiche da fare al codice per quanto riguarda l'algoritmo, altrimenti son dolori.

[fastcoder]

Sicuramente se definisci un puntatore a nodoCollegato gli devi passare un puntatore a nodoCollegato e quindi non G[0] che non sarebbe un puntatore ma una struct nodo, non &G[0] che sarebbe si un puntatore ma a struct nodo, si G[0].elencoVerticiCollegati perchè è un puntatore a struct nodoCollegato.

Un vettore mantiene i valori uno dietro l'altro come anche una lista linkata...il vettore li mantiene anche consecutivamente in memoria, mentra una lista no.
Se devi mantenere la lista dei vertici ordinata allora l'array forse non è la soluzione giusta (non sapevo di questo vincolo) e forse ti conviene tornare alla lista linkata...se devi solo evitare di riconsiderare un vertice basta che metti un flag nella struttura nodoCollegato.

[Rik142]

Infatti con G[0].elencoVerticiCollegati il programma funziona bene e non ci sono altre modifiche da fare al codice sennonchè compare un errore che mi termina il programma quando passa alle seguenti linee di codice:

int relax(int minore)
{
int riga = 0, colonna = 0;
double distanza = 0;
int r = 0, c = 0;
struct nodoCollegato *po;

po = G[minore].elencoVerticiCollegati;

while (po != NULL)
{
printf("Dal vertice %d mi dirigo in direzione del vertice %d che pesa %f\n\n",minore, po->vertice, po->peso);
if(Q[po->vertice].etichetta == -1 || Q[po->vertice].etichetta > Q[minore].etichetta + po->peso)
{
riga = minore;
colonna = po->vertice;
pi[po->vertice] = minore;
Q[po->vertice].etichetta = Q[minore].etichetta + po->peso;
distanza = Q[po->vertice].etichetta;
printf("Il nodo di provenienza del vertice %d e' = %d\n\n", po->vertice, pi[po->vertice]);
m[MAX][MAX] = crea_matrice(riga, colonna, distanza);
}
po++;
}
Q[minore].rimosso = 1;
printf("Q[%d].rimosso = %d\n\n", minore, Q[minore].rimosso);
return m[r][c];
}

Ossia: minore è il vertice preso in considerazione e fino a quando è presente nel vettore prende in esame tutti i vertici ad esso adiacenti. Il fatto è che dopo aver preso in considerazione il quarto vertice prende un successivo vertice che mi manda in errore tutto uscendo dall'esecuzione.

Dal vertice 0 mi dirigo in direzione del vertice 1 che pesa 0.412000
Il nodo di provenienza del vertice 1 e' = 0

Dal vertice 0 mi dirigo in direzione del vertice 2 che pesa 0.289000
Il nodo di provenienza del vertice 2 e' = 0

Dal vertice 0 mi dirigo in direzione del vertice 3 che pesa 0.292000
Il nodo di provenienza del vertice 3 e' = 0

Dal vertice 0 mi dirigo in direzione del vertice 4 che pesa 0.311000
Il nodo di provenienza del vertice 4 e' = 0

Dal vertice 0 mi dirigo in direzione del vertice -33686019 che pesa 0.000000 ---->>>> Esce!!!

Mi sapresti consigliare come fare perchè fino a questa notte ho provato ad inserire mille controlli per evitare che prendesse quell'ultimo valore.

[fastcoder]

non puoi fare il controllo di po == NULL per terminare il ciclo...devi fermarti quando raggiungi il numero dei vertici (ti tieni un contatore). po non è una lista linkata quindi togli il while( po != NULL ) e mettici un for( int i = 0; i < numero vertici; i++ )

[Rik142]

Ora devo fare in modo che il tutto venga fatto per un numero di volte pari al numero dei vertici. Ossia si inizia con il vertice 0 e bla bla bla, vertice 1 e bla bla bla e così via, considerando di volta in volta il vertice in questione come quello di partenza.

Scritto così è corretto??
Inoltre, per far ciò, devo riazzerare tutto e procedere come se fosse la prima volta (con la differenza che questa volta si parte da un altro vertice)?

Q[s].etichetta viene utilizzato per salvare la somma totale minima per andare da x a y,
Q[s].rimosso è utilizzato come flag da impostare a 1 nel caso il nodo in questione sia già stato preso in esame.

for(l=0; l<numerovertici; l++)
{
for(s=0; s<numerovertici; s++)
{
Q[s].etichetta = 0;
while (1)
{
s = controllaQ(Q);
if (s == -1)
break;
u = estrai_min();

if (u == -1)
break;
relax(u);
printf("La soluzione parziale e':\n\n");
for (v=0; v<n; v++)
{
printf("Q[%d].etichetta = %3lf, Q[%d].rimosso = %d pi[%d] = %3d\n", v, Q[v].etichetta, v, Q[v].rimosso, v, pi[v]);
}
printf("\n");
}
}
}

[fastcoder]

sinceramente non ci sto capendo più nulla (forse è la mia pigrizia) mi spiace ma non ho molto tempo per capire l'algoritmo che vuoi usare....se vuoi vedere se funziona perchè non lo provi ? chiedere se quello che hai scritto è giusto è un poco complicato credo...nel codice c'è estrai_min, controllaQ di cui non so un beato fico secco...se hai un problema di compilazione ti posso aiutare ma solo se mi scrivi la riga incriminata e mi dici quale errore ti da

Buon lavoro

[Rik142]

Ti capisco perfettamente. Il mio problema ora è, aldilà di quel che fanno le varie funzioni inserite all'interno del codice, se dovessi fare quel settore di codice n volte, con n che è il numero di vertici. Mi conviene utilizzare una chiamata ricorsiva passandogli il vertice corrente??
E' un algoritmo che risulta un po' costoso seppur fatto n^2 volte ma è l'ultima modifica che devo fare e poi è terminato.
Spero di essere stato un po' più chiaro di prima!!

[fastcoder]

Direi che non c'è molta differenza a fare un ciclo for o una funzione ricorsiva...entrambe le metodologie prevedono la stessa complessita computazionale (almeno credo). Quello che credo devi fare è cercare di ottimizzare la soluzione, vedendo se esiste una strada che ti permetta di trasformare un n^2 in qualcosa di meglio (non entro nel problema in questione).