Google Search

Sunday, October 30, 2011

shortest path algorithm in C program ccn lab manual


#include<stdio.h>
#include<conio.h>
void main()
{
int path[5][5],i,j,min,a[5][5],p,st=1,ed=5,stp,edp,t[5],index;

clrscr();

printf("enter the cost matrix\n");
  for(i=1;i<=5;i++)
    for(j=1;j<=5;j++)
      scanf("%d",&a[i][j]);

printf("enter  number of paths\n");
  scanf("%d",&p);

printf("enter possible paths\n");
  for(i=1;i<=p;i++)
    for(j=1;j<=5;j++)
      scanf("%d",&path[i][j]);

  
  for(i=1;i<=p;i++)
  {
    t[i]=0;
    stp=st;
    
    for(j=1;j<=5;j++)
    {
      edp=path[i][j+1];
      t[i]=t[i]+a[stp][edp];
        
      if(edp==ed)
        break;
      else
        stp=edp;
    }
  }

  min=t[st];
  index=st;
    
    for(i=1;i<=p;i++)
    {
      if(min>t[i])
      {
        min=t[i];
        index=i;
      }
    }

  printf("minimum cost %d",min);
  printf("\n minimum cost path ");

  for(i=1;i<=5;i++)
  {
    printf("--> %d",path[index][i]);
    if(path[index][i]==ed)
    break;
  }

  getch();
}



/*OUTPUT:
enter the cost matrix :
0 1 4 2 0
0 0 0 2 3
0 0 0 3 0
0 0 0 0 5
0 0 0 0 0
enter number of paths : 4
enter possible paths :
1 2 4 5 0
1 2 5 0 0
1 4 5 0 0
1 3 4 5 0
minimum cost : 4
minimum cost path :
1–>2–>5*/ 

0 comments:

Post a Comment