C Program to Construct Shortest Path Tree (SPT):

#include <stdio.h>

#include <limits.h>

#define V 5 // Define the number of vertices in the graph

// Function to find the vertex with the minimum distance value

int minDistance(int dist[], int sptSet[]) {

 int min = INT_MAX, min_index;

 for (int v = 0; v < V; v++)

 if (sptSet[v] == 0 && dist[v] <= min)

 min = dist[v], min_index = v;

 return min_index;

}

// Function to print the constructed tree and distances

void printTree(int parent[], int dist[], int src) {

 printf("Shortest Path Tree:\n");

 printf("Vertex\tDistance from Source\tParent\n");

 for (int i = 0; i < V; i++) {

 printf("%d\t\t%d\t\t%d\n", i, dist[i], parent[i]);
   }

}

// Dijkstra's algorithm to construct the shortest path tree

void dijkstra(int graph[V][V], int src) {

 int dist[V]; // dist[i] will hold the shortest distance from src to i

 int sptSet[V]; // sptSet[i] will be true if vertex i is included in SPT

 int parent[V]; // To store the shortest path tree

 // Initialize all distances as INFINITE and sptSet[] as false

 for (int i = 0; i < V; i++) {

 dist[i] = INT_MAX;

 sptSet[i] = 0;

 parent[i] = -1; // Parent of the root node will be -1

 }

 // Distance of source vertex from itself is always 0

 dist[src] = 0;

 // Find the shortest path for all vertices

 for (int count = 0; count < V - 1; count++) {

 // Pick the minimum distance vertex from the set of vertices not yet 

processed

 int u = minDistance(dist, sptSet);

 // Mark the picked vertex as processed

 sptSet[u] = 1;

 // Update dist value of the adjacent vertices of the picked vertex

 for (int v = 0; v < V; v++)

 if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + 

graph[u][v] < dist[v]) {

 dist[v] = dist[u] + graph[u][v];

 parent[v] = u; // Update the parent of vertex v

 }

 }

 // Print the constructed shortest path tree

 printTree(parent, dist, src);

}

int main() {

 // Example graph represented using an adjacency matrix
  int graph[V][V] = {

 {0, 10, 0, 0, 5}, // Node 0 to 1 has weight 10, to 4 has weight 5

 {0, 0, 1, 0, 3}, // Node 1 to 2 has weight 1, to 4 has weight 3

 {0, 0, 0, 4, 0}, // Node 2 to 3 has weight 4

 {7, 0, 6, 0, 0}, // Node 3 to 0 has weight 7, to 2 has weight 6

 {0, 3, 9, 2, 0} // Node 4 to 1 has weight 3, to 2 has weight 9, to 3 has weight 

2

 };

 // Source node for the algorithm

 int source = 0;

 // Call Dijkstra's algorithm to construct the shortest path tree

 dijkstra(graph, source);

 return 0;

}