Write a C program for finding the shortest path from a given source to any vertex in a digraph using Dijkstra’s algorithm.
/*This program prompts the user to input the number of vertices, edges, and the cost of each edge.
It then prints the adjacency matrix and calculates the shortest path from the source vertex to all other vertices using Dijkstra's algorithm.*/
#include <stdio.h>
#include <limits.h>
#define NO_EDGE -1
void printGraph(int graph[][50], int V) {
int i, j;
printf("\nThe adjacency matrix is:\n");
for (i = 0; i < V; i++) {
for (j = 0; j < V; j++) {
if (graph[i][j] == NO_EDGE)
printf("%4d ", 0);
else
printf("%4d ", graph[i][j]);
}
printf("\n");
}
}
int minDistance(int dist[], int sptSet[], int V) {
int min = INT_MAX, min_index;
int vertex;
for (vertex = 0; vertex < V; vertex++) {
if (sptSet[vertex] == 0 && dist[vertex] <= min) {
min = dist[vertex];
min_index = vertex;
}
}
return min_index;
}
void printPath(int parent[], int j) {
if (parent[j] == -1)
return;
printPath(parent, parent[j]);
printf(" -> %d", j + 1); // Adjusting to one-based index for output
}
void drawGraph(int graph[][50], int V) {
int i, j;
printf("\nGraph representation (nodes and edges):\n");
for (i = 0; i < V; i++) {
printf("Node %d:\n", i + 1);
for (j = 0; j < V; j++) {
if (graph[i][j] != NO_EDGE) {
printf(" -> Node %d (Cost: %d)\n", j + 1, graph[i][j]);
}
}
}
}
void printSolution(int dist[], int parent[], int V, int src) {
int i;
printf("Vertex\t Distance\tPath");
for (i = 0; i < V; i++) {
printf("\n%d -> %d \t\t %d\t\t%d", src + 1, i + 1, dist[i], src + 1); // Adjusting to one-based index for output
printPath(parent, i);
}
printf("\n");
}
void dijkstra(int graph[][50], int src, int V) {
int dist[50];
int sptSet[50];
int parent[50];
int i, count, vertex;
for (i = 0; i < V; i++) {
dist[i] = INT_MAX;
sptSet[i] = 0;
parent[i] = -1;
}
dist[src] = 0;
for (count = 0; count < V - 1; count++) {
int u = minDistance(dist, sptSet, V);
sptSet[u] = 1;
for (vertex = 0; vertex < V; vertex++) {
if (!sptSet[vertex] && graph[u][vertex] != NO_EDGE && dist[u] != INT_MAX && dist[u] + graph[u][vertex] < dist[vertex]) {
dist[vertex] = dist[u] + graph[u][vertex];
parent[vertex] = u;
}
}
}
printSolution(dist, parent, V, src);
}
int main() {
int V, E, i, j;
printf("****Dijkstra\'s algorithm(single-source shortest path problem)*****\n");
printf("------------------------------------------------------------------\n");
printf("Enter the number of vertices: ");
scanf("%d", &V);
int graph[50][50];
for (i = 0; i < V; i++) {
for (j = 0; j < V; j++) {
graph[i][j] = NO_EDGE;
}
}
printf("Enter the number of edges: ");
scanf("%d", &E);
printf("Enter the end vertices of each edge and its cost (one-based index):\n");
for (i = 0; i < E; i++) {
int u, v, cost;
printf("Edge %d: ", i + 1);
scanf("%d %d %d", &u, &v, &cost);
graph[u - 1][v - 1] = cost; // Adjusting to zero-based index
}
printGraph(graph, V);
drawGraph(graph, V);
int src;
printf("\nEnter the source vertex (one-based index): ");
scanf("%d", &src);
dijkstra(graph, src - 1, V); // Adjusting to zero-based index
return 0;
}
INPUT/OUTPUT
Testcase1: for the graph
****Dijkstra's algorithm(single-source shortest path problem)*****
-------------------------------------------------------------------------------------------
Enter the number of vertices: 6
Enter the number of edges: 9
Enter the end vertices of each edge and its cost (one-based index):
Edge 1: 1 2 4
Edge 2: 1 3 5
Edge 3: 2 3 11
Edge 4: 2 4 9
Edge 5: 2 5 7
Edge 6: 3 5 3
Edge 7: 4 5 13
Edge 8: 4 6 2
Edge 9: 5 6 6
The adjacency matrix is:
0 4 5 0 0 0
0 0 11 9 7 0
0 0 0 0 3 0
0 0 0 0 13 2
0 0 0 0 0 6
0 0 0 0 0 0
Graph representation (nodes and edges):
Node 1:
-> Node 2 (Cost: 4)
-> Node 3 (Cost: 5)
Node 2:
-> Node 3 (Cost: 11)
-> Node 4 (Cost: 9)
-> Node 5 (Cost: 7)
Node 3:
-> Node 5 (Cost: 3)
Node 4:
-> Node 5 (Cost: 13)
-> Node 6 (Cost: 2)
Node 5:
-> Node 6 (Cost: 6)
Node 6:
Enter the source vertex (one-based index): 1
Vertex Distance Path
1 -> 1 0 1
1 -> 2 4 1 -> 2
1 -> 3 5 1 -> 3
1 -> 4 13 1 -> 2 -> 4
1 -> 5 8 1 -> 3 -> 5
1 -> 6 14 1 -> 3 -> 5 -> 6
--------------------------------
Process exited after 114.5 seconds with return value 0
Press any key to continue . . .
Testcase2: for the graph
****Dijkstra's algorithm(single-source shortest path problem)*****
------------------------------------------------------------------
Enter the number of vertices: 9
Enter the number of edges: 14
Enter the end vertices of each edge and its cost (one-based index):
Edge 1: 1 2 4
Edge 2: 1 8 8
Edge 3: 2 8 11
Edge 4: 2 3 8
Edge 5: 8 9 7
Edge 6: 8 7 1
Edge 7: 3 9 2
Edge 8: 9 7 6
Edge 9: 7 6 2
Edge 10: 3 6 4
Edge 11: 3 4 7
Edge 12: 4 6 14
Edge 13: 6 5 10
Edge 14: 4 5 9
The adjacency matrix is:
0 4 0 0 0 0 0 8 0
0 0 8 0 0 0 0 11 0
0 0 0 7 0 4 0 0 2
0 0 0 0 9 14 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 10 0 0 0 0
0 0 0 0 0 2 0 0 0
0 0 0 0 0 0 1 0 7
0 0 0 0 0 0 6 0 0
Graph representation (nodes and edges):
Node 1:
-> Node 2 (Cost: 4)
-> Node 8 (Cost: 8)
Node 2:
-> Node 3 (Cost: 8)
-> Node 8 (Cost: 11)
Node 3:
-> Node 4 (Cost: 7)
-> Node 6 (Cost: 4)
-> Node 9 (Cost: 2)
Node 4:
-> Node 5 (Cost: 9)
-> Node 6 (Cost: 14)
Node 5:
Node 6:
-> Node 5 (Cost: 10)
Node 7:
-> Node 6 (Cost: 2)
Node 8:
-> Node 7 (Cost: 1)
-> Node 9 (Cost: 7)
Node 9:
-> Node 7 (Cost: 6)
Enter the source vertex (one-based index): 1
Vertex Distance Path
1 -> 1 0 1
1 -> 2 4 1 -> 2
1 -> 3 12 1 -> 2 -> 3
1 -> 4 19 1 -> 2 -> 3 -> 4
1 -> 5 21 1 -> 8 -> 7 -> 6 -> 5
1 -> 6 11 1 -> 8 -> 7 -> 6
1 -> 7 9 1 -> 8 -> 7
1 -> 8 8 1 -> 8
1 -> 9 14 1 -> 2 -> 3 -> 9
--------------------------------
Process exited after 191.6 seconds with return value 0
Press any key to continue . . .
No comments:
Post a Comment