Question

Consider the weighted graph below: Demonstrate Prim's algorithm starting from vertex A. Write the edges in the order they were added to the minimum spanning tree. Demonstrate Dijkstra's algorithm on the graph, using vertex A as the source. Write the vertices in the order which they are marked and compute all distances at each step.

Answer 1

#include <stdio.h>
#include <limits.h>
#define V 8

int minKey(int key[], bool set[])
{
   int min = INT_MAX, index, i;
   for(i=0;i<V;i++)
   {
       if(set[i]==false && key[i]<min)
       {
           min = key[i];
           index = i;
       }
   }  
   return index;
}

void primPrint(int p[], int graph[][V], int sum)
{
   int i;
   char arr[8] = {'A','B','C','D','E','F','G','H'};
   printf("EDGES\n");
   printf("Source - Destination - Weight\n");
   printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
   for(i=1;i<V;i++)
   {
       printf(" %c - %c - %d \n", arr[p[i]], arr[i], graph[i][p[i]]);
       sum = sum + graph[i][p[i]];
   }
   printf("Total sum of weights are : %d\n\n",sum);
}

void prim(int graph[][V])
{
   int p[V];
   int key[V];
   bool pSet[V];
   int i,b;
   for(i=0;i<V;i++)
   {
       key[i] = INT_MAX;
       pSet[i] = false;
   }
   key[0] = 0;
   p[0] = -1;
   for(i=0;i<V-1;i++)
   {
       int a = minKey(key,pSet);
       set[a] = true;
       for(b=0;b<V;b++)
       {
           if(graph[a][b] && !pSet[b] && graph[a][b] < key[b])
           {
               p[b] = a;
               key[b] = graph[a][b];
           }
       }
   }
   primPrint(p, graph, 0);
}

void dijkstraPrint(int dist[])
{
   int i;
   char arr[8] = {'A','B','C','D','E','F','G','H'};
   printf("VERTICES\n");
   printf("From Source - Weight\n");
   printf("~~~~~~~~~~~~~~~~~~~~~~~~\n");
   printf(" %c - 0\n", arr[0]);
   for(i=1;i<V;i++)
       printf(" %c - %d \n", arr[i], dist[i]);
}

void dijkstra(int graph[][V], int source)
{
   int dist[V];
   bool dSet[V];
   int i,b;
   for(i=0;i<V;i++)
   {
       dist[i] = INT_MAX;
       dSet[i] = false;
   }
   dist[source] = 0;
   for(i=0;i<V-1;i++)
   {
       int a = minKey(dist,dSet);
       dSet[a] = true;
       for(b=0;b<V;b++)
       {
           if(graph[a][b] && !dSet[b] && dist[a]!=INT_MAX && dist[a]+graph[a][b] < dist[b])
               dist[b] = dist[a] + graph[a][b];
       }
   }
   dijkstraPrint(dist);
}

int main()
{
   int graph[V][V] = {{0, 5, 0, 0, 4, 0, 0, 0},
               {5, 0, 6, 0, 3, 14, 10, 0},
               {0, 6, 0, 1, 0, 0, 9, 17},
               {0, 0, 1, 0, 0, 0, 0, 12},
               {4, 3, 0, 0, 0, 11, 0, 0},
               {0, 14, 0, 0, 11, 0, 7, 0},
               {0, 10, 9, 0, 0, 7, 0, 15},
               {0, 0, 17, 12, 0, 0, 15, 0}};
   prim(graph);
   dijkstra(graph,0);
   return 0;
}

agilaa@agilaa: /Desktop/pro/C EX (M) (96%) 4)) 12:04 PM * agilaa@agilaa:/Desktop/pro/C$ g++ graph.c-o graph agilaa@agilaa:~/Desktop/pro/C$./graph PRIM S ALGORITHM EDGES Source Destination Weight 8 4 12 Total sum of weights are 42 DIJKSTRA S ALGORITHM- VERTICES From Source Weight 12 15 15 24 agilaa@agilaa:-/Desktop/pro/csI

I have included both (a) and (b) in the same program as different functions.