Trend Posts
Author
View LUQMAN's profile
Showing posts with label dijkstras algorithm. Show all posts
Showing posts with label dijkstras algorithm. Show all posts
Monday, July 21, 2014
/*From a given vertex in a weighted connected graph, find shortest paths to other vertices using Dijkstra's algorithm.*/
#include<stdio.h>
int cost[10][10],n,sv,i,j,v,count=0,w,min,t,w,dist[10],visited[10],path[10];
void dj();
void print();
void main()
{
printf("\n\nEnter the number of nodes\n\n");
scanf("%d",&n);
printf("\n\nEnter the cost matrix\n\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&cost[i][j]);
printf("\nEntered cost matrix is:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d\t",cost[i][j]);
printf("\n");
}
printf("\nEnter the source node\n");
scanf("%d",&sv);
dj();
print();
}
void dj()
{
for(i=1;i<=n;i++)
{
visited[i]=0;
dist[i]=cost[sv][i];
if(cost[sv][i]==999)
path[i]=0;
else
path[i]=sv;
}
visited[sv]=1;
while(count<=n)
{
min=999;
for(w=1;w<=n;w++)
if(dist[w]<=min&&!visited[w])
{
min=dist[w];
v=w;
}
visited[v]=1;
count++;
for(w=1;w<=n;w++)
if(dist[w]>dist[v]+cost[v][w])
{
dist[w]=dist[v]+cost[v][w];
path[w]=v;
}
}
}
void print()
{
for(w=1;w<=n;w++)
if(visited[w]==1 && w!=sv)
{
printf("\nThe sorted distance between %d-->%d=%d",sv,w,dist[w]);
t=path[w];
printf("\nThe path is:\n");
printf("%d",w);
while(t!=sv)
{
printf("-->%d",t);
t=path[t];
}
printf("<-->%d",sv);
}
}
Subscribe to:
Posts (Atom)