Dijkstra Algorithm

#include "stdio.h"
#include "conio.h"
#include "graphics.h"
#include "stdlib.h"
void fillcol(int ltx,int lty ,int col)
{
int i,j;
lty=lty+1;
ltx=ltx+1;
for(j=0;j<69;j++)
{
for(i=0;i<69;i++)
{
putpixel(ltx+i,lty,col);
}
lty=lty+1;
}
}
void draw(int *var,int len)
{
int gm,gd=DETECT,i,j,x=10,y=10,temp=10,k,data[17][2],l,count=1,tt;
initgraph(&gd,&gm,"c:\tc\bgi");
for(i=0;i<4;i++)
{
temp=temp+70;
y=temp;
x=10;
for(j=0;j<4;j++)
{
setcolor(3);
data[count][0]=x;
data[count][1]=y;
count++;
rectangle(x,y,x+70,y+70);
fillcol(x,y,4);
x=x+70;
}
}
for(i=0;i<=len;i++)
{
tt = var[i];
rectangle(data[tt][0],data[tt][1],data[tt][0]+70,data[tt][1]+70);
fillcol(data[tt][0],data[tt][1],0);
}
setcolor(8);
outtextxy(35,100,"1");
outtextxy(105,100,"2");
outtextxy(175,100,"3");
outtextxy(235,100,"4");
outtextxy(35,170,"5");
outtextxy(105,170,"6");
outtextxy(175,170,"7");
outtextxy(235,170,"8");
outtextxy(35,240,"9");
outtextxy(105,240,"10");
outtextxy(175,240,"11");
outtextxy(235,240,"12");
outtextxy(35,310,"13");
outtextxy(105,310,"14");
outtextxy(175,310,"15");
outtextxy(235,310,"16");
setcolor(13);
settextstyle(6, HORIZ_DIR, 4);
outtextxy(250,10,"INTELLIGENT DRIVING");
}
void main()
{
int cost[17][17],dist[17],s[17],prev[17];
int sp ,ep,i,j,k,t=0,path[20],dec,temp,min=32767,u;
clrscr();
for(i=0;i<20;i++)
{
path[i]=0;
}
for(i=0;i<17;i++)
{
for(j=0;j<17;j++)
{
if(i==j)
{
cost[i][j]=0;
}
if( abs(j-i)==4)
{
cost[i][j]=cost[j][i]=1;
}
if( abs(i-j)==1)
{
cost[i][j]=cost[j][i]=1;
}
if(i!=j && abs(j-i)!=4 && abs(i-j)!=1)
{
cost[i][j]=cost[j][i]=32767;
}
}
}
printf("enter the source name
");
scanf("%d",&sp);
printf("enter the destination name
");
scanf("%d",&ep);
for(i=0;i<17;i++)
{
prev[i]=sp;
cost[0][i]=0;
cost[i][0]=0;
}
for(i=0;i<17;i++)
{
dist[i]=0;
s[i]=0;
}
for(i=1;i<=16;i++)
{
dist[i]=cost[sp][i];
}
s[sp]=1;
dist[sp]=0;
for(i=2;i<=16;i++)
{
for(k=1;k<=16;k++)
{
if(min > dist[k] && s[k]!=1)
{
min=dist[k];
u=k;
break;
}
min=32767;
}
s[u]=1;
for(j=1;j<=16;j++)
{
if(cost[u][j]==1)
{
if(s[j]==0)
{
if(dist[j] > (dist[u]+ cost[u][j]))
{
dist[j]=dist[u]+cost[u][j];
prev[j]=u;
}
}
}
}
}
clrscr();
t=ep;
dec=dist[ep];
path[dec]=t;
for(i=0;i {
dec--;
t=prev[t];
path[dec]=t;
}
draw(&path[0],dist[ep]);
getch();
closegraph();
}

Related Links :