[C]: Algoritmi Dijkstra, Bellman-Ford e Floyd-Warshall

[quagmire]

ciao a tutti io avrei bisogno di alcune delucidazioni riguardo l'implementazione degli algoritmi di dijkstra , bellman-ford e floyd-warshall in C.. il problema è che ho gia scritto il codice del programma che comprende tra le altre cose un generatore di grafi random (un po rudimentale!) pero c sn dei bug nelle funzioni per la ricerca dei cammini minimi che (anche dopo ore e ore di debug) nn sn riuscito a eliminare... se volete posso postarvi l intero codice sorgente basta che mi diate una mano plz.... sto perdendo il contatto con la realta!!!

[alka]

Ciao e benvenuto nel forum di Programmazione.

Ti segnalo da subito la lettura del nostro Regolamento che contiene tutte le norme da seguire per partecipare correttamente a quest'area del forum.

In modo particolare, devi sempre indicare il linguaggio utilizzato nel titolo della discussione, indicando la versione nel caso in cui ne esistesse più di una, assieme ad una sintesi breve ma significativa ed esplicativa del problema.

Ho spostato inoltre la discussione nel forum generico, poiché era stata aperta nell'area dedicata specificatamente ai linguaggi Microsoft per il .NET Framework.

Detto questo, ciao e...buon forum!

[quagmire]

perfetto ...

si tratta sl di prendere un po d confidenza col regolamento del forum...

cmq ribadisco il mio appello semi-disperato a chi per un giorno vuol sentirsi un buon samaritano ........
cmq questo è il codice del programma:

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MAX 50

struct nodo //celle grafo
{
int info;
int peso;
struct nodo *next;
};

struct coda // celle coda per SP
{
int info;
struct coda *next;
};

int num_random(int minimo, int massimo)
{
int diff;

diff = massimo-minimo;

if (diff != 0)
return minimo + (rand()+time(NULL))%(diff);
else
return minimo;
}

int ins_num_vert()
{
int nodi;

while(1)
{
printf("\nNumero di nodi (max %d):\n",MAX);

fflush(stdin);
scanf("%d",&nodi);

if(nodi==0)
exit(0);

if(nodi>MAX)
puts("\n ERRORE: superato max nodi");
else
break;
}

return nodi;
}

char ins_num_edges()
{
char archi;

while(1)
{
puts("\nNumero di archi (a - alto,b - medio,c - basso):");

fflush(stdin);
scanf("%c",&archi);

if(archi=='0')
exit(0);

if(archi=='a'||archi=='b'||archi=='c'||archi=='A'| |archi=='B'||archi=='C')
break;
else
puts("\n ERRORE inserimento");
}

return archi;
}

char ins_w_edges()
{
char peso;

while(1)
{
puts("\nPeso archi (a - positivo,b - positivo e negativo,c - negativo):");

fflush(stdin);
scanf("%c",&peso);

if(peso=='0')
exit(0);

if(peso=='a'||peso=='b'||peso=='A'||peso=='B'||pes o=='c'||peso=='C')
{
if(peso=='c'||peso=='C')
{
printf("La possibilita\' di inserire esclusivamente archi di peso negativo serve per aumentare le probabilita\' di presenza di cicli di peso negativo all\'interno del grafo, al fine di verificare la correttezza del funzionamento dell\'algoritmo di bellman-ford.\n\n");
system("pause");
}
break;
}
else
puts("\n ERRORE inserimento");
}

return peso;
}

int check_adj(int info, int adiac[MAX],int j)
{
int i;

for(i=0;i<j;i++)
if(info==adiac[i])
return 0;

return 1;
}

struct nodo* gen_vert(int Nnodi,char Narchi,char Parchi, int i)
{
struct nodo *nuovo, *testa=NULL;
int j,N,var,flag,adiac[MAX];

//adiacenti=(int)malloc(Nnodi*(sizeof(int)));//vettore di supporto utilizzato per evitare ripetizioni nella generaz di archi

if(Narchi=='a')
N=num_random(((Nnodi/3)*2)+1,Nnodi);

if(Narchi=='b')
N=num_random((Nnodi/3)+1,(Nnodi/3)*2);

if(Narchi=='c')
N=num_random(1,(Nnodi/3));

for(j=0;j<N;j++)
{
nuovo=(struct nodo*)malloc(sizeof(struct nodo));

while(1)
{
nuovo->info=num_random(0,Nnodi);

if(nuovo->info==i)
continue;//eliminazione self-loop
else
{
if(j!=0)//il primo arco va sempre bene
flag=check_adj(nuovo->info,adiac,j);//controllo archi gia scelti

if(flag==1||j==0)
break;//arco valido
else
continue;//arco gia esistente se ne genera un altro
}
}
adiac[j]=nuovo->info;

if(Parchi=='a'||Parchi=='A')
nuovo->peso=num_random(1,100);
if(Parchi=='b'||Parchi=='B')
{
var=num_random(1,3); //per evitare che la random restituisca uno 0 che darebbe
if(var==1) //problemi nell'interpretazione della matrice di adiacenza
nuovo->peso=num_random(1,100);
else
nuovo->peso=num_random(-100,-1);
}
if(Parchi=='c'||Parchi=='C')
nuovo->peso=num_random(-100,-1);

nuovo->next=testa;
testa=nuovo;
}

return testa;

}

void print_graph(struct nodo *G[],int adMat[][MAX],int Nnodi)
{
int i,j,cont;
struct nodo *temp;

puts("\nlista adiacenza:\n");

printf("nodo 0 --> "); //stampa lista

for(i=0;i<Nnodi;i++)
{
if(temp==NULL)
cont=0;

temp=G[i];

while(temp!=NULL)
{
if(cont==0)
printf("nodo %d --> ",i);

printf(" %d(%d), ",temp->info,temp->peso);

temp=temp->next;
cont++;
}

printf("\n");
}

printf("\n\n");

puts("matrice adiacenza:\n");

for(i=0;i<Nnodi;i++) //stampa matrice
{
for(j=0;j<Nnodi;j++)
printf(" %3d ",adMat[i][j]);
printf("\n");
}

puts("\n");
system("pause");
}

int extract_min(struct coda **testa,int *d)
{
struct coda *temp,*min,*prec=NULL,*prec_min=NULL;
int u;

min=*testa;
temp=*testa;

while(temp!=NULL)
{
if((d[temp->info]>1 && d[temp->info]<d[min->info])||d[temp->info]==-1)
{
min=temp;
prec_min=prec;
}

prec=temp;//si scorre la coda aggiornando temp e prec
temp=temp->next;
}

u=min->info; //trovato min
//eliminazione nodo gia aggiunto alla soluzione (cioe min, il nodo piu vicino alla sorgente tra quelli della fontiera)
if(prec_min==NULL)//min è il primo della della lista: allora la testa diventa il suo next
*testa=(*testa)->next;
else
prec_min->next=min->next;//altri casi

free(min);//lib memoria

return u;

}

void enqueue(struct coda **testa, int i)
{
struct coda *nuovo;

nuovo=(struct coda*)malloc(sizeof(struct coda));
nuovo->info=i;
nuovo->next=*testa;
*testa=nuovo;
}

int ins_source(int Nnodi)
{
int i,cont,sorgente;

while(1)
{
cont=0;
puts("nodo sorgente:");

fflush(stdin);
scanf("%d",&sorgente);

for(i=0;i<Nnodi;i++)
if(sorgente!=i)
cont++;

if(cont==Nnodi)
{
printf("ERRORE inserimento\n\n");
continue;
}
else
break;
}

return sorgente;
}

void print_SP(int Nnodi, int *d, int *pgreco)
{
int i;

for(i=0;i<Nnodi;i++)
printf("d[%d]=%3d, p[%d]=%3d\n",i,d[i],i,pgreco[i]);

printf("\n");
system("pause");

}

void dijkstra(struct nodo *G[],int Nnodi,int sorgente)
{
int i,u,d[MAX],pgreco[MAX];
struct coda *testa=NULL;
struct nodo *temp;
//initialize_single_source
for(i=0;i<Nnodi;i++)
{
d[i]=-1;
pgreco[i]=-1;
}

d[sorgente]=0;

for(i=0;i<Nnodi;i++)
enqueue(&testa,i);

while(testa!=NULL)
{
u=extract_min(&testa,d);

temp=G[u]; //relax
while(temp!=NULL)
{
if(d[temp->info]==-1||(d[temp->info]>(d[u]+temp->peso)))
{
d[temp->info]=d[u]+temp->peso;
pgreco[temp->info]=u;
}
temp=temp->next;
}
}

print_SP(Nnodi,d,pgreco);
}

int bellman_ford(struct nodo *G[],int Nnodi,int sorgente,int flag)
{
int i,j,d[MAX],pgreco[MAX];
struct coda *testa=NULL;
struct nodo *temp;
//initialize_single_source
for(i=0;i<Nnodi;i++)
{
d[i]=-1;
pgreco[i]=-1;
}

d[sorgente]=0;

for(j=0;j<Nnodi;j++)
{
for(i=0;i<Nnodi;i++)
{
temp=G[i];
while(temp!=NULL)
{
if(d[temp->info]==-1||(d[temp->info]>(d[i]+temp->peso)))
{
d[temp->info]=d[i]+temp->peso;
pgreco[temp->info]=i;
}
temp=temp->next;
}
}
}

for(i=0;i<Nnodi;i++)
{
temp=G[i];
while(temp!=NULL)
{
if(d[temp->info]>(d[i]+temp->peso))
{
printf("\nsono presenti cicli di peso negativo, impossibile determinare il cammino minimo\n");

if(flag==1)
printf("\nimpossibile utilizzare l\'algoritmo di floyd-warshall...\n\n");

system("pause");
return 1;
}
temp=temp->next;
}
}

if(flag==0)
print_SP(Nnodi,d,pgreco);

return 0;
}

int gen_ad_mat(struct nodo *G[],int i, int j )
{
struct nodo *temp;

temp=G[i];

while(temp!=NULL)
{
if(temp->info==j)
return temp->peso;

temp=temp->next;
}

return 0;
}

void floyd_warshall(int adMat[][MAX],int Nnodi)
{
int dist[MAX][MAX];
int padre[MAX][MAX];
int i,j,k;

for (i=0;i<Nnodi;i++) //inizializzazione matrici dist e padre
for (j=0;j<Nnodi;j++)
{
dist[i][j]=adMat[i][j];

if(adMat[i][j]!=0)
padre[i][j]=i;
else
padre[i][j]=-1;
}

for (k=0;k<Nnodi;k++)
for (i=0;i<Nnodi;i++)
for (j=0;j<Nnodi;j++)
if (dist[i][j]>dist[i][k]+dist[k][j])
{
dist[i][j]=dist[i][k]+dist[k][j];
padre[i][j]=padre[k][j];
}


printf("D[%d]:\n",Nnodi);// D[]: matrice delle distanze
for(i=0;i<Nnodi;i++)
{
for(j=0;j<Nnodi;j++)
printf(" %d ",dist[i][j]); //stampa matrici
printf("\n");
}

printf("\n");

printf("P[%d]:\n",Nnodi);//P[]:matrice dei predecessori
for(i=0;i<Nnodi;i++)
{
for(j=0;j<Nnodi;j++)
printf(" %d ",padre[i][j]);
printf("\n");
}

printf("\n");

system("pause");
}

void main()
{
int i,j,sorgente,Nnodi,adMat[MAX][MAX],flag;
char creaz,stamp,sceltaSP,Parchi,Narchi;
struct nodo *G[MAX];


while(1)
{
system("cls");

puts("NOME: MATRICOLA:");
puts("ELABORATO DI ALGORITMI E STRUTTURE DATI: CAMMINI MINIMI");

puts("\n\n[0] --> esci...");

puts("\n\n[g] --> crea grafo...\n");

fflush(stdin);
scanf("%c",&creaz);

if(creaz!='g'&&creaz!='G')
{
if(creaz=='0')
exit(0);

system("cls");
continue;
}
else
{
Nnodi=ins_num_vert();
Narchi=ins_num_edges();
Parchi=ins_w_edges();

for(i=0;i<Nnodi;i++)
G[i]=gen_vert(Nnodi,Narchi,Parchi,i);//generazione vertici del grafo in lista di adiacenza

for(i=0;i<Nnodi;i++)
for(j=0;j<Nnodi;j++)
adMat[i][j]=gen_ad_mat(G,i,j); //generazione matrice di adiacenza
}

puts("\n[s] --> stampa lista e matrice di adiacenza (qualunque tasto per proseguire)... ");

fflush(stdin);
scanf("%c",&stamp);

switch(stamp)
{
case'0':
exit(0);

case's':
case'S':
print_graph(G,adMat,Nnodi);

default:
while(1)
{
puts("\nRICERCA DEI CAMMINI MINIMI(a - Single Source SP,b - All Pairs SP):");

fflush(stdin);
scanf("%c",&sceltaSP);

if(sceltaSP=='a'||sceltaSP=='A')
{
//puts("\n");

sorgente=ins_source(Nnodi); //controllo errori di input nell inserimento della sorgente

if(Parchi=='a'||Parchi=='A') //se gli archi sono positivi uso dijkstra
{
printf("\nalgoritmo di dijkstra...\n\n");

dijkstra(G,Nnodi,sorgente);

break;
}

if(Parchi=='b'||Parchi=='B'||Parchi=='c'||Parchi== 'C') //se gli archi sn anche negativi uso bellman-ford
{
printf("\nalgoritmo di bellman-ford...\n");

bellman_ford(G,Nnodi,sorgente,0);

break;
}
}
if(sceltaSP=='b'||sceltaSP=='B')
{
if(Parchi=='b'||Parchi=='B'||Parchi=='c'||Parchi== 'C')
{
puts("\nalgoritmo di bellman-ford...");

flag=bellman_ford(G,Nnodi,0,1);//controllo cicli negativi
}
else
flag=0;

if(flag==0)
{
printf("\nnon ci sono cicli di peso negativo\n\n");

printf("algoritmo di floyd-warshall...\n\n");

floyd_warshall(adMat,Nnodi);
}
break;

}
else
{
if(sceltaSP=='0')
exit(0);
else
{
printf("ERRORE inserimento\n");
continue;
}
}
}
}
}
return;
}

[bDaniele]

http://it.wikipedia.org/wiki/Algoritmo_di_Dijkstra

[quagmire]

se qualcuno ha l implementazione in c di questi algoritmi me li mandi per favore..........

[alka]

Originariamente inviato da quagmire
se qualcuno ha l implementazione in c di questi algoritmi me li mandi per favore..........

Se possibile, è meglio pubblicarli qui, o pubblicare un link agli algoritmi.

Il forum non è tendenzialmente un luogo in cui ci si accorda per assistenza privata: non rientra nello spirito del forum.

[quagmire]

ma infatti intendevo questo....
forse mi sono spiegato male..........