/*a) Write a C program for the implementation of Dijkstra’s shortest path
algorithm for finding
shortest path from a given source vertex using adjacency cost matrix.*/
#include <stdio.h>
#include <limits.h>
#define MAX_VERTICES 100
// Function to find the vertex with the minimum distance value
int minDistance(int dist[], int sptSet[], int vertices) {
int min = INT_MAX, minIndex;
for (int v = 0; v < vertices; v++) {
if (!sptSet[v] && dist[v] < min) {
min = dist[v];
minIndex = v;
}
}
return minIndex;
}
// Function to print the constructed distance array
void printSolution(int dist[], int vertices) {
printf("Vertex \tDistance from Source\n");
for (int i = 0; i < vertices; i++) {
printf("%d \t%d\n", i, dist[i]);
}
}
// Function to implement Dijkstra's algorithm for a given graph and source
vertex
void dijkstra(int graph[MAX_VERTICES][MAX_VERTICES], int src, int vertices) {
int dist[MAX_VERTICES];
int sptSet[MAX_VERTICES];
for (int i = 0; i < vertices; i++) {
dist[i] = INT_MAX;
sptSet[i] = 0;
}
// Distance from source vertex to itself is always 0
dist[src] = 0;
// Find the shortest path for all vertices
for (int count = 0; count < vertices - 1; count++) {
int u = minDistance(dist, sptSet, vertices);
// Mark the picked vertex as processed
sptSet[u] = 1;
// Update dist value of the adjacent vertices of the picked vertex.
for (int v = 0; v < vertices; v++) {
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] +
graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
// Print the constructed distance array
printSolution(dist, vertices);
}
int main() {
int vertices;
// Input the number of vertices
printf("Input the number of vertices: ");
scanf("%d", &vertices);
if (vertices <= 0 || vertices > MAX_VERTICES) {
printf("Invalid number of vertices. Exiting...\n");
return 1;
}
int graph[MAX_VERTICES][MAX_VERTICES];
// Input the adjacency matrix representing the weighted graph
printf("Input the adjacency matrix for the graph (use INT_MAX for infinity):
\n");
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
scanf("%d", &graph[i][j]);
}
}
int source;
// Input the source vertex
printf("Input the source vertex: ");
scanf("%d", &source);
if (source < 0 || source >= vertices) {
printf("Invalid source vertex. Exiting...\n");
return 1;
}
// Perform Dijkstra's algorithm
dijkstra(graph, source, vertices);
return 0;
}
/*Write a C program for the implementation of Floyd Warshall’s algorithm for
finding all pairs
shortest path using adjacency cost matrix.*/
#include<stdio.h>
#define MAX_VERTICES 100
void floydWarshall (int graph[MAX_VERTICES][MAX_VERTICES],int vertices)
{
int dist[vertices][vertices], i, j, k;
// Initialize the solution matrix same as input graph matrix.
for (i = 0; i < vertices; i++)
for (j = 0; j < vertices; j++)
dist[i][j] = graph[i][j];
// Update the solution matrix by picking all vertices one by one
for (k = 0; k < vertices; k++)
{
for (i = 0; i < vertices; i++)
{
for (j = 0; j < vertices; j++)
{
// If vertex k is on the shortest path from i to j,
// then update the value of dist[i][j]
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
printSolution(dist,vertices);
}
void printSolution(int dist[MAX_VERTICES][MAX_VERTICES],int vertices)
{
printf ("Following matrix shows the shortest distances between every pair of
vertices \n");
for (int i = 0; i < vertices; i++)
{
for (int j = 0; j < vertices; j++)
{
if (dist[i][j] == 9999)
printf("%7s", "INF");
else
printf ("%7d", dist[i][j]);
}
printf("\n");
}
}
int main()
{
int vertices,graph[MAX_VERTICES][MAX_VERTICES];
// Input the number of vertices
printf("Input the number of vertices: ");
scanf("%d", &vertices);
printf("Input the adjacency matrix for the graph (use INT_MAX for infinity):
\n");
for (int i = 0; i < vertices; i++)
{
for (int j = 0; j < vertices; j++)
{
scanf("%d", &graph[i][j]);
}
}
/*int graph[V][V] = { {0, 5, 9999, 10},
{9999, 0, 3, 9999},
{9999, 9999, 0, 1},
{9999, 9999, 9999, 0}
};*/
floydWarshall(graph,vertices);
return 0;
}
