PDA

View Full Version : سوال: مشكل در مورد الگوريتم dijkstra با زبان c++



hitman2004
جمعه 03 اردیبهشت 1389, 15:28 عصر
سلام
من الگوريتم دايجسترا رو با C++‎ نوشتم. اين برنامه تويه اولين سوال جواب درست رو مي ده اما اگه يه مسير ديگه رو ازش بپرسي ديگه كار نمي كنه و برنامه تموم نميشه و جواب نمي ده. بعضي وقتا هم جواب اشتباه مي ده. اگه ممكنه راهنمايي كنيد.
ممنون
كد برنامه :




#include<stdio.h>
#include<conio.h>

int g[20][20],visit[20],d[20],p[20];
int v,e;
int min=32767;

void creategraph()
{
int a,b,i,j,w;
printf("Enter the no of vertices : ");
scanf("%d",&v);
printf("\nEnter no. of edges : ");
scanf("%d",&e);
for(i=1;i<=v;i++)
for(j=1;j<=v;j++)
g[i][j]=0;
for(i=1;i<=v;i++)
{
visit[i]=0;
d[i]=min;
}
for(i=1;i<=e;i++)
{
printf("\nEnter edges & weight : ");
scanf("%d %d %d",&a,&b,&w);
g[a][b]=g[b][a]=w;
}
}

void dijkstra()
{
int src,des,c,i,dc,l,x;
printf("\nEnter source and destination : ");
scanf("%d %d",&src,&des);
c=src;
d[src]=0;
visit[src]=1;
dc=d[c];

while(visit[des]!=1)
{
for(i=1;i<=v;i++)
{
if(g[c][i]!=0)
if(visit[i]==0)
if(d[i]>g[c][i]+dc)
{
d[i]=g[c][i]+dc;
p[i]=c;
}
}
min=32767;
for(i=1;i<=v;i++)
{
if(visit[i]==0)
if(d[i]<min)
{
min=d[i];
c=i;
}
}
dc=d[c];
visit[c]=1;
}
printf("\nShortest distance from %d to %d ",src, des);
printf("%d",d[des]);
printf("\nPath=\n");
l=des;
do
{
x=p[l];
printf("\nVertex %d is connected to %d\n ",l,x);
l=x;

}while(l!=src);

}

void main()
{
char ch,ci;
clrscr();
do
{ creategraph();
do{
dijkstra();
printf("IF WANT TO CONTINUE WITH SAME DATA PRESS Y : ");
fflush(stdin);
scanf("%c",&ci);
}while(ci=='y');
printf("\nDo u wish to continue : ");
fflush(stdin);
scanf("%c",&ch);
} while(ch!='n');
}