PROGRAM IN LINUX C FOR PRIM'S ALGORITHM (FINDING THE SHORTEST PATH IN GRAPH)

#include<stdio.h>

#define IN 99

int dist[10],path[10];

int extract_min(int Q[], int n)

{

int i,temp[10],t=0,pos;

for(i=0;i<n;i++)

{

if(Q[i]!=-1)

temp[i]=1;

else

temp[i]=0;

}

for(i=0;i<n;i++)

{

if(t==0 && temp[i]==1)

{pos =i;

t=1;

continue;

}

if(temp[i]==1)

if(dist[i]<dist[pos])

pos=i;

}

return pos;

}

int contain(int Q[],int v,int n)

{

int i;

for(i=0;i<n;i++)

if(Q[i]==v+1)

return 1;

return 0;

}

int isempty(int Q[], int n)

{

int i;

for(i=0;i<n;i++)

{

if(Q[i]!=-1)

return 0;

}

return 1;

}

void initialize(int n,int s)

{

int i;

for(i=0;i<n;i++)

{

dist[i]=IN;

path[i]=-1;

}

dist[s]=0;

}

//Module which implement prim algorithm

void prim(int edge[10][10],int n,int s)

{

int Q[10],i,u,v,alt;

//Initialization step

initialize(n,s);

for(i=0;i<n;i++)

Q[i]=i+1;

while(isempty(Q,n)==0)

{

u=extract_min(Q,n);

Q[u]=-1;

if(dist[u]==IN)

break;

for(i=0;i<n;i++)

{

if(edge[u][i]!=0 && edge[u][i]!=IN)

{

v=i;

if(edge[u][i]<dist[v] && contain(Q,v,n)==1)

{

dist[v]=edge[u][i];

path[v]=u+1;

}

}

}

}

}

void main()

{

int n,edge[10][10],i,j,s,t,wt=0;

//clrscr();

printf("Enter total number of vertices::");

scanf("%d",&n);

//printf("\nEnter Edge matrix in row major order");

//printf("Enter %d for Infinity::\n");

for(i=0;i<n;i++)

{

for(j=i+1;j<n;j++)

{

printf("Enter the edge between %d and %d: ",i+1,j+1);

scanf("%d",&edge[i][j]);

edge[j][i]=edge[i][j];

}

edge[i][i]=0;

}

printf("\n");

printf("Enter the source for MST: ");

scanf("%d",&s);

prim(edge,n,s-1);

printf("\nPATH OF MINIMUM SPANNING TREE is\n");

for(i=0;i<n;i++)

{

if(s-1==i)

continue;

if(dist[i]==IN)

{

printf("PATH from %d to %d not exist\n",i+1,s);

}

else

{

printf("PATH from %d to %d is %d:",i+1,s,i+1);

t=i;

for(j=1;j<n;j++)

{

printf("<--%d",path[t]);

if(path[t]==s)

break;

t=path[t]-1;

}

printf("\n");

}

wt+=dist[i];

 }

printf("\nMinimum Weight of a Graph is %d",wt);

//getch();

}