Assigment Day 6:
Question 6.1
Write a program in C that implements the following:-
i) A graph is supplied by the user as shown in the figure along with a starting node s
ii) The program finds the minimum cost of reaching every vertex along its corresponding
parent or intermediate node with respect to the starting node s and prints the minimum
cost and the intermediate parent node.
Test Case :G3, Output: d[s]=0 ,p[s]=NULL, d[y]=5,p[y]=s, d[t]=7,p[t]=y,
d[x]=8,p[x]=t,d[z]=7,p[z]=y
Code:
#include <stdio.h>
#include <stdbool.h>
#define MAX_NODES 1000
#define INF 99999
int graph[MAX_NODES][MAX_NODES];
int distance[MAX_NODES];
bool visited[MAX_NODES];
int parent[MAX_NODES];
int minDistance(int n) {
int minIndex = -1, minDist = INF;
for (int i = 0; i < n; i++) {
if (!visited[i] && distance[i] < minDist) {
minDist = distance[i];
minIndex = i;
}
}
return minIndex;
}
void dijkstra(int start, int n) {
for (int i = 0; i < n; i++) {
distance[i] = INF;
visited[i] = false;
parent[i] = -1;
}
distance[start] = 0;
for (int i = 0; i < n-1; i++) {
int u = minDistance(n);
visited[u] = true;
for (int v = 0; v < n; v++) {
if (!visited[v] && graph[u][v] && distance[u] != INF && distance[u]+graph[u][v] <
distance[v]) {
distance[v] = distance[u]+graph[u][v];
parent[v] = u;
}
}
}
}
void printResult(int start, int n) {
char vertex;
for (int i = 0; i < n; i++) {
switch (i) {
case 0: vertex = 's'; break;
case 1: vertex = 't'; break;
case 2: vertex = 'x'; break;
case 3: vertex = 'y'; break;
case 4: vertex = 'z'; break;
}
printf("d[%c]=%d, p[%c]=", vertex, distance[i], vertex);
if (parent[i] == -1) {
printf("NULL\n");
} else {
printf("%c\n", parent[i]+'s');
}
}
}
int main() {
int n = 5; // number of vertices
int start = 0; // starting vertex
// adjacency matrix of the graph
int g3[5][5] = {{0, 10, 0, 5, 0},
{0, 0, 1, 2, 0},
{0, 0, 0, 0, 4},
{0, 3, 9, 0, 2},
{7, 0, 6, 0, 0}};
// copy the graph to the global variable
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
graph[i][j] = g3[i][j];
}
}
dijkstra(start, n);
printResult(start, n);
return 0;
}
Output: