DISTANCE VECTOR ROUTING ALGORITHM

#include<stdio.h>

#include<conio.h>

#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)

              {

                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].len)

            {

               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)

       {

              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