Design and implement C/C++ Program to find shortest paths from a given vertex in a weighted connected graph to other vertices using Dijkstra's algorithm
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 10 // Maximum number of vertices allowed
#define INF 99 // Representation of infinity (a large number)
// Global arrays to hold distances, predecessors, and visited status
int d[MAX_VERTICES]; // Distance array
int p[MAX_VERTICES]; // Predecessor array (to reconstruct paths)
int visited[MAX_VERTICES]; // Visited flag array
// Function to implement Dijkstra's algorithm
void dijk(int a[MAX_VERTICES][MAX_VERTICES], int s, int n) {
int u, v, i, j, min;
// Initialization: Set all distances to infinity and all predecessors to -1
for (v = 0; v < n; v++) {
d[v] = INF; // Unknown distance from source to v
p[v] = -1; // No predecessor for v yet
visited[v] = 0; // Mark all nodes as unvisited
}
d[s] = 0; // Distance from source to itself is always 0
// Main loop for Dijkstra's algorithm
for (i = 0; i < n; i++) {
min = INF;
// Find the unvisited vertex with the smallest distance
for (j = 0; j < n; j++) {
if (d[j] < min && visited[j] == 0) {
min = d[j];
u = j; // u is the vertex with the smallest tentative distance
}
}
visited[u] = 1; // Mark the selected vertex as visited
// Update the distances of neighbors of u
for (v = 0; v < n; v++) {
// Update d[v] only if:
// - there is an edge from u to v
// - v is not visited
// - the path through u offers a shorter distance to v
if ((d[u] + a[u][v] < d[v]) && (u != v) && visited[v] == 0) {
d[v] = d[u] + a[u][v]; // Update distance
p[v] = u; // Update predecessor
}
}
}
}
// Recursive function to print the shortest path from source to vertex v
void path(int v, int s) {
if (p[v] != -1) // If predecessor exists
path(p[v], s); // Recurse to print previous vertex
if (v != s) // Don't print source again
printf("->%d ", v); // Print this vertex
}
// Function to display the shortest paths and their distances
void display(int s, int n) {
int i;
for (i = 0; i < n; i++) {
if (i != s) {
printf("%d ", s); // Start path display from source
path(i, s); // Show path to vertex i
}
if (i != s)
printf("=%d ", d[i]); // Show distance from source to vertex i
printf("\n");
}
}
int main() {
int a[MAX_VERTICES][MAX_VERTICES]; // Adjacency matrix
int i, j, n, s;
// Input: number of vertices
printf("Enter the number of vertices: ");
scanf("%d", &n);
// Input: adjacency matrix (graph representation)
printf("Enter the weighted matrix:\n");
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
scanf("%d", &a[i][j]);
// Input: source vertex from which shortest paths are to be calculated
printf("Enter the source vertex: ");
scanf("%d", &s);
// Call Dijkstra's algorithm
dijk(a, s, n);
// Display shortest paths from source to all other vertices
printf("The shortest path between source %d to remaining vertices are:\n", s);
display(s, n);
return 0;
}
OUTPUT:
Enter the number of vertices: 5
Enter the weighted matrix:
999 3 999 7 999
3 999 4 2 999
999 4 999 5 6
7 2 5 999 4
999 999 6 4 999
Enter the source vertex: 0
The shortest path between source 0 to remaining vertices are:
0 ->1 =3
0 ->1 ->2 =7
0 ->1 ->3 =5
0 ->1 ->3 ->4 =9
=== Code Execution Successful ===