Newsgroup: it.comp.lang.c++
Titolo: percorso tra due nodi di un grafo. aiutoooo!!

Qulacuno sa gentilmente indicarmi un sito o spedirmi un e-mail con una
funzione che dati due nodi di un grafo mi trova il percorso tra loro due (i
nodi adiacenti ad ogni nodo sono messi in liste di adiacenza)?? vi prego
aiutatemi.
Se non conoscete nessun sito date almeno uno sguardo a questa funzione che
ho fatto e ditemi dov'è l'errore che a me, proprio non gira.
#include <stdio.h>
#include <stdlib.h>
struct nodo{
int nome;
struct nodo *successivo;
};
typedef struct nodo NODO;
typedef NODO *PUNT;
void cercapercorso(PUNT g[20], int n, int d, PUNT p);
main()
{
int i, j, n, s, d;
PUNT p, g[20];
printf("immettere il numero di nodi del grafo\n");
scanf("%d", &n);
for(i=0;i<n;i++)
g[i]=NULL;
printf("immetti i nodi collegati o -1 per uscire\n");
for(i=0;i<n;i++){
printf("nodi collegati al nodo %d\n", i);
do{
scanf("%d", &j);
if(j>=0 && j<n && j!=i){
p=(PUNT)malloc(sizeof(NODO));
if(p!=NULL){
p->nome=j;
p->successivo=g[i];
g[i]=p;}}}
while(j!=-1);}
for(i=0;i<n;i++){
printf("i nodi collegati al nodo %d sono:\n", i);
while(g[i]!=NULL){
printf("%d -> ", g[i]->nome);
g[i]=g[i]->successivo;}
printf("NULL\n");}
printf("\n\nimmettere il nodo di partenza\n");
scanf("%d", &s);
printf("immettere il nodo di arrivo\n");
scanf("%d", &d);
p=(PUNT)malloc(sizeof(NODO));
p->nome=s;
p->successivo=NULL;
cercapercorso(g,n,d,p);
if(p->successivo==NULL)
printf("cammino inesistente\n");
else{
while(p!=NULL){
printf("%d -> ", p[i]);
p=p->successivo;}
printf("fine\n");}
      system("PAUSE");
      return 0;
}
void cercapercorso(PUNT g[20], int n, int d, PUNT p)
{
int j, inp, escluso, finito, q[20];
PUNT k, t, f;
for(j=0;j<n;j++)
q[j]=0;
k=p;
while(k!=NULL && k->nome!=d){
f=g[k->nome];
finito=0;
inp=2;
escluso=1;
while(f!=NULL && finito==0 && (inp==2 || escluso==1)){
j=g[k->nome]->nome;
inp=q[j];
escluso=q[j];
if(j==d)
finito =1;
else
f=f->successivo;}
if(f==NULL){
q[k->nome]=1;
k=p;
while((k->successivo)->successivo!=NULL)
k=k->successivo;
k->successivo=NULL;}
else{
q[k->nome]=2;
t=(PUNT)malloc(sizeof(NODO));
if(t!=NULL){
t->nome=j;
t->successivo=NULL;
k->successivo=t;
k=k->successivo;}}}
}

 PUNT p, g[20];
Anche dichiarare le variabili al momento dell'utilizzo (e non tutte
all'inizio) aiuta.
        Mauro

 all'inizio) aiuta.
In C++ certamente, ma ho l'imprssione che il programma sia scritto in C!!!
(ed allora dichiararle all'inizio e' richiesto!)
In altre parole credo fosse stato meglio postare quel messaggio sul gruppo
di C o su quello di algoritmi.... (anche se non si puo' considerare OT!)
Tommy

 vi prego aiutatemi.
http://ioi.dsi.unimi.it
c'e` una dispensa che descrive l'algoritmo di Dijckstra, ovvero proprio 
quello che ti serve.
ciao Anto
-- 
"Computer science is not about computers any more than astronomy
is about telescopes." -- EW Dijkstra

 (ed allora dichiararle all'inizio e' richiesto!)
beh falso per il c99
     In C99 and C++, but not C89, we can define a variable in the
     initialization portion of a for statement; the scope of this variable
is
     the code block of the for-loop, or local to that loop.  Often we need a
     control variable only for a loop, so this practice is becoming quite
     common.
e non del tutto vero per il c89.. e' sufficente che sia all'inzio di un
blocco
Sbirish.

      In C99 and C++, but not C89, we can define a variable in the
Si, ok non ho detto che non si possano dichiarare variabili nei cicli in
C99, ho detto che dichiarare tutto all'inizio e' tipico della codifica C.
Nella codifica C tradizionale e' richiesto. Ma forse e' colpa mia e sono
stato poco chiaro, allora grazie per la puntualizzazione.
Tommy

 Tommy
Infatti non sei chiaro neanche ora. All' inizio di cosa?
Sbirish.

"sbirish" <sbi...@dontspam.me.tnx> wrote

e' mezzanotte qua in Inghilterra e sono tornato da una festa e non ho voglia
di risponderti... polemiche polemiche polemiche, ti ho pure ringraziato per
la puntualizzazione, ma a voi non va mai bene.... Ad ogni modo quello che ho
scritto mi sembra chiaro anche ora che ho bevuto qualche birra, quindi...
Tommy


bisognerebbe mettere nel manifesto di questo newsgroup che č OT
scrivere post dopo che si č stati ad una festa, si č bevuto della
birra e i propri messaggi sembrano chiarissimi.

 ho fatto e ditemi dov'è l'errore che a me, proprio non gira.
Risolvere questo problema e' estremamente semplice, mentre non lo e'
leggere il codice che hai accluso, considerando che non
contiene neanche un commento e che non hai spiegato minimamente che
algoritmo usi.
Soprattutto non hai spiegato se vuoi trovare il percorso piu' breve
o se ti va bene qualunque percorso !! E' molto diverso !
Per cercare il percorso piu' breve, per esempio, puoi fare cosi':
(Trovi sicuramente tanti documenti se fai una ricerca con Google)
segni tutti i nodi come "non visti" (basta un campo int nella struttura
nodo), poi parti dal nodo di partenza, lo segni come visto a distanza 0,
e segni tutti quelli adiacenti  come "visti a distanza 1", poi per tutti
  quelli distanti 1 segui le  adiacenze, e se trovi nodi non visti li
segni come nodi "visti a distanza 2" e cosi' via fino a che non finisci
i nodi raggiungibili oppure trovi quello destinazione.
Mentre esplori i nodi cosi' ti memorizzi, (in un campo opportuno
aggiunto alla struttura nodo) il nodo padre (quello del livello prima
che mi raggiunge). In questo modo quando arrivi a quello destinazione
devi solo seguire i cammini a rovescio per avere il percorso.
Ciao,
g.

 is about telescopes." -- EW Dijkstra
Quale delle due versioni del cognome è vera? Io voto la seconda ;)
Pace all'anima sua (L'ho lisciato per poco ad Austin :( )
Ciao
Giuseppe

Giuseppe wrote:

anche io voto per la seconda... ma chi e` quello sgrammaticato che ha 
scritto "Dijckstra"? :-))
ciao Anto
-- 
"Computer science is not about computers any more than astronomy
