lab4

 #include <stdio.h> 

#include <stdbool.h> 

#include <limits.h> 

#define MAX_VERTICES 10  // Maximum number of vertices 

#define INF INT_MAX 

// A function to find the vertex with the minimum distance value, from the 

set of vertices not yet included in the shortest path tree 

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

int min = INF, min_index; 

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

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

min = dist[v], min_index = v; 

return min_index; 

} 

// A utility function to print the constructed distance array 

void printSolution(int dist[], int V) { 

printf("Vertex \t\t Distance from Source\n"); 

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

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

} 

// Dijkstra's algorithm for adjacency matrix representation of the graph 

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

int dist[MAX_VERTICES];  // The output array. dist[i] will hold the 

shortest distance from src to i 

bool sptSet[MAX_VERTICES];  // sptSet[i] will be true if vertex i is 

included in the shortest path tree 

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

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

dist[i] = INF, sptSet[i] = false; 

dist[src] = 0; 

// Find shortest path for all vertices 

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

int u = minDistance(dist, sptSet, V); 

sptSet[u] = true; 

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

21 

Department of CSE (CY), RNSIT         

IV Semester          

BCSL404 – ADA LABORATORY 

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

< dist[v]) 

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

} 

printSolution(dist, V); 

} 

// Driver code 

int main() { 

int V, E; 

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

scanf("%d", &V); 

printf("Enter the number of edges: "); 

scanf("%d", &E); 

int graph[MAX_VERTICES][MAX_VERTICES] = {{0}}; 

printf("Enter the source vertex, destination vertex, and weight for each 

edge:\n"); 

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

int source, dest, weight; 

scanf("%d %d %d", &source, &dest, &weight); 

graph[source][dest] = weight; 

graph[dest][source] = weight; // Assuming undirected graph 

} 

dijkstra(graph, 0, V); 

return 0; 

}