4 2 9 1 5 1 SolutionASSUMING s0t1x2z3y4 include include defi

Solution

ASSUMING s=0,t=1,x=2,z=3,y=4

#include<stdio.h>
#include<limits.h>
#define V 5
int findMinKey(int *dist,int sptset[])
{
   int min=INT_MAX,i,min_index;
   for(i=0;i<V;i++)
   {
       if(sptset[i]==0 && dist[i]<min)
       {
           min=dist[i];
           min_index=i;
       }
   }
   return min_index;
}
void printSol(int graph[V][V],int *dist)
{
   int i;
   printf(\"vertex\\tDist frm Src\ \");
   for(i=0;i<V;i++)
   printf(\"%d\\t%d\ \",i,dist[i]);
   printf(\"\ \");
}
void primSPT(int graph[V][V],int src)//O(V^2)takes
{
   int sptset[V],dist[V];
   int count,i,u,v;
   for(i=0;i<V;i++)
   {
       dist[i]=INT_MAX;
       sptset[i]=0;
   }
   dist[src]=0;
   for(count=0;count<V-1;count++)
   {
       u=findMinKey(dist,sptset);
       sptset[u]=1;
       for(v=0;v<V;v++)
       {
           if(graph[u][v] && sptset[v]==0 && dist[u]!=INT_MAX && dist[u]+graph[u][v]<dist[v])
           {
               dist[v]=graph[u][v]+dist[u];
           }
       }
   }
   printSol(graph,dist);
}
int main()
{
   /*
   ASSUMING s=0,t=1,x=2,z=3,y=4
   */
   int graph[V][V]={{0, 10, 0, 0, 5},
{0, 0, 1, 0, 4},
{0, 0, 0, 4, 0},
{7, 0, 6, 0, 0},
{0, 3, 9, 2, 0},
};
   primSPT(graph,0);//Time Complexity of the implementation is O(V^2)
   return 0;
}