SHORTEST PATH ROUTING ALGORITHM (DIJKSTRA ALGORITHM)
By karthick
, in
IMPLEMENTATION OF SHORTEST PATH ROUTING ALGORITHM (DIJKSTRA ALGORITHM)
,
0 Comments
Program
#include<stdio.h>
#define
INF 999
int
main()
{
int
i,j,k,n,src,des,index;
int
dis[10][10],cost[10][10],path[10][10][20],size[20][20];
char
ch;
printf("\n\n\t
PROGRAM IMPLEMENTATION TO FIND THE SHORTEST PATH ");
printf("\n\n\t
============================================== ");
printf("\n\n
Enter the Number of vertices : ");
scanf("%d",&n);
//Gettig
the cost of the paths
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("\n\n
Enter the cost from the path %d to %d
:",i,j);
scanf("%d",&cost[i][j]);
if(cost[i][j]
== 0)
{
dis[i][j]=INF;
}
else
{
dis[i][j]=cost[i][j];
}
path[i][j][1]=i;
path[i][j][2]=j;
size[i][j]=2;
}
}
printf("\n\t****Adjacency
Matrix****\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("\t%d",dis[i][j]);
}
printf("\n");
}
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
//If
the cost is less than the previous cost
if(dis[i][j]>dis[i][k]+dis[k][j])
{
dis[i][j]=dis[i][k]+dis[k][j];
//update
path by isnerting the vertex and the size
size[i][j]=size[i][j]+1;
index=size[i][j];
path[i][j][index]=path[i][j][index-1];
path[i][j][index-1]=k;
}
}
}
}
do
{
printf("\n\n
Enter the source Vertex : ");
scanf("%d",&src);
printf("\n\n
Enter the destination vertex : ");
scanf("%d",&des);
printf("\n\n
The shortest Path from %d to %d is :
%d",src,des,dis[src][des]);
printf("\n\n
The Shortest root from the source vertex %d to the destination vert
ex
%d is :\n",src,des);
for(k=1;k<=size[src][des];k++)
{
printf("\t->%d",path[src][des][k]);
}
printf("\n\n
Do you want to continue(y/n) :
");
scanf("
%c",&ch);
}
while(ch=='y');
return
0;
}
OUTPUT
[11ca013@mcalinux
network]$ cc 16diji.c
[11ca013@mcalinux
network]$ ./a.out
PROGRAM IMPLEMENTATION TO FIND THE
SHORTEST PATH
=================================================
Enter the Number of vertices : 4
Enter the cost from the path 1 to 1 :2
Enter the cost from the path 1 to 2 :4
Enter the cost from the path 1 to 3 :5
Enter the cost from the path 1 to 4 :1
Enter the cost from the path 2 to 1 :5
Enter the cost from the path 2 to 2 :3
Enter the cost from the path 2 to 3 :6
Enter the cost from the path 2 to 4 :7
Enter the cost from the path 3 to 1 :2
Enter the cost from the path 3 to 2 :3
Enter the cost from the path 3 to 3 :4
Enter the cost from the path 3 to 4 :6
Enter the cost from the path 4 to 1 :1
Enter the cost from the path 4 to 2 :2
Enter the cost from the path 4 to 3 :3
Enter the cost from the path 4 to 4 :4
****Adjacency Matrix****
2
4 5 1
5
3 6
7
2
3 4 6
1
2 3 4
Enter the source Vertex :
3
Enter the destination vertex :
4
The shortest Path from 3 to 4 is : 3
The Shortest root from the source vertex 3 to
the destination vertex 4 is :
->3 ->1
->4
Do you want to continue(y/n) : n
0 Response to "SHORTEST PATH ROUTING ALGORITHM (DIJKSTRA ALGORITHM) "
Post a Comment