Data Communication network programs (DCN)
Data Communication network(DCN) Program for shortest path routing algorithm (Dijkstra’s algorithm).
Write a program for shortest path routing algorithm (Dijkstras algorithm).
Program Code:
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
#define infinity 9999
#define true 1
#define false 0
int *ct;
int **makeinfinity(int n);
void main()
{
int w,v,x,y,i,j,p=0;
int **cost,*D,*visited,vert,edge;
clrscr();
printf("\n Enter No of vertices :: ");
scanf("%d",&vert);
cost=makeinfinity(vert);
D =(int *)malloc(vert*(sizeof(int)));
ct =(int *)malloc(vert*(sizeof(int)));
for(i=1;i<=vert;i++)
visited[i]=false;
printf("\n Enter No of edges :: ");
scanf("%d",&edge);
for(i=0;i<edge;i++)
{
printf("\n Enter Edge%d :: ",i+1);
scanf("%d%d",&x,&y);
printf("\n Enter cost of edge from %d to %d :: ",x,y);
scanf("%d",&cost[x][y]);
}
for(i=2;i<=vert;i++)
{
if(p==0)
{
for(j=1;j<=vert;j++)
D[j]=cost[1][j];
D[1]=infinity;
p++;
ct=D;
}
w=findmin(D,vert);
visited[w]=true;
for(v=2;v<=vert;v++)
{
if(visited[v]!=true)
D[v]=min(D[v],D[w]+cost[w][v]);
}
}
for(i=2;i<=vert;i++)
printf("\nCost of path 1 to %d = %d",i,D[i]);
getch();
free(D);
free(cost);
free(ct);
}
int ** makeinfinity(int n)
{
int i,j,**a;
a=(int **)malloc(n*(sizeof(int)));
for(i=0;i<=n;i++)
a[i]=(int *)malloc(n*(sizeof(int)));
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
a[i][j]=infinity;
return a;
}
int min(int x,int y)
{
if(x>y)
return y;
else
return x;
}
int findmin(int *D,int vert)
{
int min,i,w;
min=D[2];
w=2;
for(i=2;i<=vert;i++)
{
if(D[i]<min)
{
min=D[i]; w=i;
}
}
D[w]=min;
return w;
}
Output:
Enter No of edges :: 6
Enter Edge1 :: 1 2
Enter cost of edge from 1 to 2 :: 5
Enter Edge2 :: 1 4
Enter cost of edge from 1 to 4 :: 4
Enter Edge3 :: 2 1
Enter cost of edge from 2 to 1 :: 7
Enter Edge4 :: 2 4
Enter cost of edge from 2 to 4 :: 2
Enter Edge5 :: 3 2
Enter cost of edge from 3 to 2 :: 3
Enter Edge6 :: 4 3
Enter cost of edge from 4 to 3 :: 1
Cost of path 1 to 2 = 5
Cost of path 1 to 3 = 5
Cost of path 1 to 4 = 4