Lab Program-6
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 <limits.h>
#define MAX 100 // Maximum number of vertices
// Function to find the vertex with the minimum distance
int minDistance(int dist[], int visited[], int n) {
int min = INT_MAX, min_index = -1;
for (int v = 0; v < n; v++) {
if (!visited[v] && dist[v] <= min) {
min = dist[v];
min_index = v;
}
}
return min_index;
}
// Function to print shortest path distances
void printSolution(int dist[], int n, int src) {
printf("\nShortest distances from source vertex %d:\n", src);
for (int i = 0; i < n; i++) {
printf("To vertex %d = %d\n", i, dist[i]);
}
}
// Dijkstra's algorithm function
void dijkstra(int graph[MAX][MAX], int src, int n) {
int dist[MAX]; // Stores shortest distances
int visited[MAX]; // Marks visited vertices
// Initialize distances and visited array
for (int i = 0; i < n; i++) {
dist[i] = INT_MAX;
visited[i] = 0;
}
dist[src] = 0; // Distance to source is 0
// Find shortest path for all vertices
for (int count = 0; count < n - 1; count++) {
int u = minDistance(dist, visited, n);
visited[u] = 1;
// Update distances of adjacent vertices
for (int v = 0; v < n; v++) {
if (!visited[v] && graph[u][v] && dist[u] != INT_MAX &&
dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
// Print the result
printSolution(dist, n, src);
}
// Main function to get input and call Dijkstra's algorithm
int main() {
int graph[MAX][MAX];
int n, src;
printf("Enter number of vertices: ");
scanf("%d", &n);
printf("Enter the adjacency matrix (0 for no edge):\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &graph[i][j]);
}
}
printf("Enter the source vertex (0 to %d): ", n - 1);
scanf("%d", &src);
dijkstra(graph, src, n);
return 0;
}
OUTPUT:
Enter number of vertices: 5
Enter the adjacency matrix (0 for no edge):
0 10 0 0 5
00102
00040
70600
03920
Enter the source vertex (0 to 4): 0
Shortest distances from source vertex 0:
To vertex 0 = 0
To vertex 1 = 8
To vertex 2 = 9
To vertex 3 = 7
To vertex 4 = 5
Lab Program-7
Design and implement C/C++ Program to obtain the Topological ordering
of vertices in a given digraph.
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
int graph[MAX][MAX]; // Adjacency matrix
int visited[MAX]; // Visited array
int stack[MAX]; // Stack to store topological order
int top = -1; // Stack top
// Function to perform DFS and push vertices to stack
void dfs(int v, int n) {
visited[v] = 1;
for (int i = 0; i < n; i++) {
if (graph[v][i] && !visited[i]) {
dfs(i, n);
}
}
stack[++top] = v; // Push after visiting all adjacent vertices
}
// Function to perform Topological Sort
void topologicalSort(int n) {
for (int i = 0; i < n; i++) {
visited[i] = 0; // Initialize all as not visited
}
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs(i, n);
}
}
// Print topological order
printf("\nTopological Order of the given graph:\n");
while (top != -1) {
printf("%d ", stack[top--]);
}
printf("\n");
}
int main() {
int n;
printf("Enter the number of vertices: ");
scanf("%d", &n);
printf("Enter the adjacency matrix of the directed graph (0 or 1 only):\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &graph[i][j]);
}
}
topologicalSort(n);
return 0;
}
OUTPUT:
Enter the number of vertices: 6
Enter the adjacency matrix of the directed graph (0 or 1 only):
011000
000100
000110
000001
000001
000000
Topological Order of the given graph:
024135
