Description:
Problem statement: Given a graph and a source
vertex in graph, find shortest paths from source to all vertices in the given
graph.
Algorithm
- Create a shortest path tree set
that keeps track of vertices included in shortest path tree, i.e., whose
minimum distance from source is calculated and finalized. Initially, this
set is empty.
- Assign a distance value to all vertices in the
input graph. Initialize all distance values as INFINITE. Assign distance
value as 0 for the source vertex so that it is picked first.
- While shortest
path tree set doesn’t include all vertices
a)
Pick a vertex u which is not there in shortest path
tree set and has minimum distance value.
b)
Include u to shortest path tree set
c)
Update distance value of all adjacent vertices of
u. To update the distance values, iterate through all adjacent vertices. For
every adjacent vertex v, if sum of distance value of u (from source) and weight
of edge u-v, is less than the distance value of v, then update the distance
value of v.
Solution:
#include<stdio.h>
void dij(int,int);
int min(int);
int a[20][20],dis[20],s[20],i,j;
void main()
{
int v,n;
printf("Enter
the no of nodes\n");
scanf("%d",&n);
printf("Enter
the cost matrix\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
printf("Enter
the vertex\n");
scanf("%d",&v);
dij(v,n);
for(i=1;i<=n;i++)
printf("From
%d to %d is %d\n",v,i,dis[i]);
}
void dij(int v,int n)
{
int
w,u,k;
for(i=1;i<=n;i++)
{
s[i]=0;
dis[i]=a[v][i];
}
s[v]=1;
dis[v]=0;
for(i=2;i<=n;i++)
{
u=min(n);
s[u]=1;
for(w=1;w<=n;w++)
{
if(dis[w]
> dis[u]+a[u][w])
dis[w]=dis[u]+a[u][w];
else
dis[w]=dis[w];
}
}
}
int min(int n)
{
int
i,p,min=99;
for(i=1;i<=n;i++)
{
if(min
> dis[i] && s[i]==0)
{
min=dis[i];
p=i;
}
}
return
p;
}
OUTPUT :
Enter the no of nodes
5
Enter the cost matrix
0 3 99 7 99
3 0 4 2 99
99 4 0 5 6
7 2 5 0 4
99 99 6 4 0
Enter the vertex
1
From 1 to 1 is 0
From 1 to 2 is 3
From 1 to 3 is 7
From 1 to 4 is 5
From 1 to 5 is 9
No comments:
Post a Comment