djkstras(shortest path)

#include
#include
void sort(void);
static int dsp[10][10],nodes;
struct
{ char src;
char dest;
int length;
}stemp,permanent[10]={' ',' ',0},temp[10]={' ',' ',-1};
static int perm,tem;
void main()
{ int i,j,k,l,m,n=0,point;
char initial,dest,path[10]={' '};
clrscr();
printf("\t\t Shortest Path (Dijkstra's algorithm)");
printf("\n*******************************************************");
printf(“\nEnter the number of nodes:”);
scanf(“%d”,&nodes);
printf(“\nEnter the adjacency matrix for the graph:\n”);

for(i=0;i {
for(j=0;j scanf(“%d”,&dsp[I][j]);
}
fflush(stdin);
printf("\n enter the source node:");
scanf("%c",&initial);
fflush(stdin);
printf("\n Enter the destination node:");
scanf("%c",&dest);

permanent[perm].src=initial;
permanent[perm].dest=initial;
permanent[perm++].length=0;
i=permanent[perm-1].dest-97;

for(j=0;j {
if(i!=j)
{
if(dsp[i][j]>0)
{
temp[tem].src=permanent[perm-1].src;
temp[tem].dest=j+97;
temp[tem++].length=dsp[i][j];
}
}
}

sort();

while(tem>=0)
{
j=permanent[perm-1].dest-97;
for(i=0;i {
if(i!=initial-97)
{
if(dsp[j][i]>0)
{
l=-1;
for(k=0;k
{
if(permanent[k].dest==(i+97))
l=k;
}
for(k=0;k {
if(temp[k].dest==(i+97))
l=k;
}
if(l<0)
{
temp[tem].src=j+97;
temp[tem].dest=i+97;

for(m=0;m {
if(permanent[m].dest==temp[tem].src)
n=permanent[m].length;
}
temp[tem++].length=dsp[j][i]+n;
}
else
{
for(m=0;m {
if(permanent[m].dest==j+97)
{
n=permanent[m].length+dsp[j][i];
break;
}
else
n=dsp[j][i];
}

if((n {
temp[l].length=n;
temp[l].src=j+97;
temp[l].dest=i+97;
}
}
}
}
}

sort();
}

printf("\nShortest path:\n");
printf("From %c to %c is:",initial,dest);
for(i=0;i {

if(permanent[i].dest==dest)
{
point=i;
n=i;
break;
}
}

i=0;

for(j=perm;j>0;j--)
{
if(permanent[j-1].dest==permanent[point].src)
{
path[i++]=permanent[point].dest;
point=j-1;
}
}

path[i]=initial;

for(j=i;j>=0;j--)
printf("%c ",path[j]);

printf("\t length=%d",permanent[n].length);

getch();

}

void sort()
{ int i,j,k;
for(i=0;i<=tem;i++)
{ k=1;

for(j=0;j<=tem;j++)
{
if((temp[j].length <= temp[j+1].length))
{
stemp=temp[j];
temp[j]=temp[j+1];
temp[j+1]=stemp;
k=0;
}
}

if(k)
break;

}

permanent[perm++]=temp[tem-1];
temp[tem-1].src=' ';
temp[tem-1].dest=' ';
temp[tem-1].length=-1;
tem--;

}