#include<stdio.h>
#include<conio.h>
#define member 1
#define nomember 0
#define infinity 999
typedef struct edge
{
int wt;
}edge;
int n;
edge g[10][10];
/*
The main function
Parameter Passing Method :None
Called By : The O.S.
Calls :,get(),shrt()
*/
void main()
{
int src,dest;
void get();
int shrt(int,int);
printf("\n Program For Shortest Path Algorithm\n");
printf("enter no of vertices: ");
scanf("%d",&n);
get();
printf("\nEnter The Source");
scanf("%d",&src);
printf("\nEnter The Destination: ");
scanf("%d",&dest);
printf("\nshortest path:%d",shrt(src,dest));
getch();
}
/*
The get function
Parameter Passing Method :None
Called By : main
Calls : none
*/
void get()
{
int i,j,v1,v2;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("enter The edge Of V%d TO V%d:",i,j);
scanf("%d",&g[i][j].wt);
}
printf("\n");
}
}
/*
The shrt function
Input Parameter:source and destination
Parameter Passing Method :By value
Called By : main
Calls : none
*/
int shrt(int src,int dest)
{
int small,perm[10],dist[10],current,start,new1;
int k=1,temp,i;
for(i=0;i<=n;i++)
{
perm[i]=0;
dist[i]=infinity;
}
perm[src]=1;
dist[src]=0;
current=src;
printf("\n\tpath is : %d",src);
while(current!=dest)
{
small=infinity;
start=dist[current];
for(i=1;i<=n;i++)
{
if(perm[i]==0)
{
new1=start+g[current][i].wt;
if(new1<dist[i])
dist[i]=new1;
if(dist[i]<small)
{
small=dist[i];
temp=i;
}
}
}
current=temp;
perm[current]=1;
k++;
printf(" %d",current);
}
return(small);
}