#include<stdio.h>
#include<conio.h>
#define max 10
#define INFINITY 1000
char node[max];
int ind[max];
int d[max];
char p[max];
int w[max][max];
char edge[2*max*max][2];
int e_size;
int n_size;
int in_dat()
{
printf("\n Enter the number of nodes : ");
scanf("%d",&n_size);
fflush(stdin);
for(int i=0;i<n_size;i++)
node[i] = 97+i;
e_size = 0;
for(int i=0;i<n_size;i++)
{
w[i][i] = 0;
for(int j=i+1;j<n_size;j++)
{
printf("\n Enter the weight of edge '%c' to '%c': ",97+i,97+j);
scanf("%d",&w[i][j]);
if(w[i][j] != 0)
{
edge[e_size][0] = 97+i;
edge[e_size][1] = 97+j;
e_size++;
}
printf("\n Enter the weight of edge '%c' to '%c': ",97+j,97+i);
scanf("%d",&w[j][i]);
if(w[j][i] != 0)
{
edge[e_size][0] = 97+j;
edge[e_size][1] = 97+i;
e_size++;
}
}
}
return 0;
}
int dis_dat()
{
printf("\n The Path adjacent matrix \n");
for(int i=0;i<n_size;i++)
printf("\t%c",97+i);
for(int i=0;i<n_size;i++)
{
printf("\n%c",97+i);
for(int j=0;j<n_size;j++)
printf("\t%d",w[i][j]);
}
getch();
fflush(stdin);
return 0;
}
int dijkstra()
{
char s;
do
{
printf("\n Enter the starting point : ");
scanf("%c",&s);
}while(s<97||s>=97+n_size);
for(int i=0;i<n_size;i++)
{
d[i] = INFINITY;
p[i] = ' '; // NULL
ind[i] = 0;
}
int si = s-97;
d[si] = 0;
int in=0;
int min;
int dd;
int tp;
while(in < n_size)
{
min = INFINITY;
ind[si] = 1;
for(int i=0;i<n_size;i++)
{
if(w[si][i] != 0)
{
dd = d[si] + w[si][i];
if(d[i] > dd)
{
d[i] = dd;
p[i] = node[si];
}
}
if(min > d[i] && ind[i] == 0)
{
min = d[i];
tp = i;
}
}
si = tp;
ind[si] = 1;
++in;
}
getch();
printf("\n ..... The Results ..... \n");
printf("\n \td\tp");
for(int i=0;i<n_size;i++)
printf("\n%c\t%d\t%c",node[i],d[i],p[i]);
return 0;
}
int main()
{
in_dat();
dis_dat();
dijkstra();
getch();
return 0;
}
No comments:
Post a Comment