Source Code

Get programs to develop you own applications.

Dijkstra’s algorithm in C

Posted by mohammedmoulana on April 3, 2012

/*Implement Dijkstra’s algorithm to compute the Shortest path through a Graph*/

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

int c[10][10],d[10],s[10],n,dist[10],temp[10];
void main()
{
int i,j,k,min,tot;
clrscr();
printf(“\n\t Enter number of nodes:”);
scanf(“%d”,&n);
printf(“\n\t Enter the cost matrix (if no path then enter 99):\n”);
for(i=[10];i<=n;i++)
for(j=1;j<=n;j++)
{
printf(“\t Enter cost from %d to %d : “,i,j);
scanf(“%d”,&c[i][j]);
}
clrscr();
printf(“\nThe matrix is : \n”);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf(“%5d”,c[i][j]);
printf(“\n”);
}
for(i=1;i<=n;i++)
{
dist[i]=i;
d[i]=c[1][i];
}
s[1]=1;
dist[1]=99;
printf(“\nThe shortest distance is :”);
for(i=2;i<=n;i++)
{
min=mindist();
s[i]=min;
dist[min]=99;
for(j=2;j<=n;j++)
{
if(dist[j]!=99)
{
if(d[j]>d[min]+c[min][j])
d[j]=d[min]+c[min][j];
}
}
printf(“\n\t”);
for(k=1;k<=n;k++)
{
if(k<=i)
printf(“%d “,s[k]);
else
printf(”  “);
}
printf(“\t\t”);
}
printf(“\n”);
for(i=2;i<=n;i++)
{
printf(“\nCost from 1 –> %d : “,i);
if(d[i]>=99)
printf(“INF “);
else
printf(“%d “,d[i]);
getch();
}
}

int mindist()
{
int i,min=100,ret;
for(i=1;i<=n;i++)
{
if(dist[i]==99)
continue;
if(d[i]<min)
{
min=d[i];
ret=i;
}
}
return(ret);
}
}

About these ads

One Response to “Dijkstra’s algorithm in C”

  1. I have been checking out a few of your posts and i can claim pretty good stuff.
    I will definitely bookmark your site.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
Follow

Get every new post delivered to your Inbox.

Join 443 other followers

%d bloggers like this: