Ash's Blog

DISTANCE VECTOR ROUTING ALGORITHM

Posted on: February 23, 2011

DISTANCE VECTOR ROUTING ALGORITHM
#include
#include
#define LIMIT 10
#define INFINITY 10000
int n,m,i,j,mi,dist[LIMIT][LIMIT],a[LIMIT],adj[LIMIT],sn,dn,c=0,x[LIMIT],min;
main()
{
clrscr();
printf(“Enter no.of nodes::”);
scanf(“%d”,&n);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
dist[i][j]=-1;
for(i=1;i<=n;i++)
{
printf(“\nEnter distance for %d node:”,i);
for(j=1;j<=n;j++)
if(dist[i][j]==-1)
{
if(i==j)
{
dist[i][j]=0;
printf(“\n 0”);
}
else
{
scanf(“%d”,&m);
dist[i][j]=dist[j][i]=m;
}
}
else
printf(“\n%d”,dist[i][j]);
}
printf(“\ndistance matrix is:”);
for(i=1;i<=n;i++)
{
printf(“\n”);
for(j=1;j<=n;j++)
printf(“%d\t”,dist[i][j]);
}
printf(“\nnEnter the sorce node :”);
scanf(“%d”,&sn);
printf(“Enter the distance node:”);
scanf(“%d”,&dn);
j=1;m=0;
for(i=1;i<=n;i++)
{
if(dist[sn][i]>0)
{
m++;
adj[j++]=i;
}
}
min=0;
mi=INFINITY;
for(i=1;i<=m;i++)
{
printf(“\nVector table for %d to all nodes:”,adj[i]);
for(j=1;j<=n;j++)
{
if(adj[i]==j)
x[j]=0;
else
x[j]=spath(adj[i],j,min);
if(j==dn)
if(x[j] {
mi=x[j];
c=adj[i];
}
printf(“\n%d”,x[j]);
}
}
for(i=1;i<=n;i++)
{
if(i==sn)
a[i]=0;
else
if(i==dn)
a[i]=dist[sn][c]+mi;
else
a[i]=spath(sn,i,min);
}
printf(“\nNew vector table for %d node:”,sn);
for(i=1;i<=n;i++)
printf(“\n%d”,a[i]);
getch();
}

int spath(int s,int t,int min)
{
struct state
{
int pred;
int len;
enum{permanent,tentative}label;
}state[LIMIT];
int i=1,k;
struct state *p;
for(p=&state[i];p<=&state[n];p++)
{
p->pred=0;
p->len=INFINITY;
p->label=tentative;
}
state[t].len=0;
state[t].label=permanent;
k=t;
do
{
for(i=1;i<=n;i++)
if(dist[k][i]!=0 && state[i].label==tentative)
{
if(state[k].len+dist[k][i] {
state[i].pred=k;
state[i].len=state[k].len+dist[k][i];
}
}
k=0;
min=INFINITY;
for(i=1;i<=n;i++)
if(state[i].label==tentative && state[i].len {
min=state[i].len;
k=i;
}
state[k].label=permanent;
} while(k!=s);
return(min);
}

output
Enter no.of nodes::4

Enter distance for 1 node:
0
1
2
0

Enter distance for 2 node:
1
0
0
4

Enter distance for 3 node:
2
0
0
8

distance matrix is:
0 1 2 0
1 0 0 4
2 0 0 8
0 4 8 0
Enter the source node :3
Enter the distance node:2

Vector table for 1 to all nodes:
0
1
2
5
Vector table for 4 to all nodes:
5
4
7
0
New vector table for 3 node:
2
3
0
7

Advertisements

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 up !

Enter your email address to follow this blog and receive notifications of new posts by email.

iTweet :

Error: Twitter did not respond. Please wait a few minutes and refresh this page.

Where are you?

%d bloggers like this: