Scribd
Upload
7 views2 pages

Dijkstra's Algorithm in C Programming

The document contains a C program that implements Dijkstra's algorithm to find the shortest path in a graph represented by an adjacency matrix. It initializes distances, selects the unvisited vertex with the smallest distance, updates neighboring vertices, and prints the shortest distance and path from a specified starting vertex to a destination vertex. The program also includes user input for the number of vertices, the adjacency matrix, and the starting and destination vertices.

Uploaded by

Aritra Das
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
7 views2 pages

Dijkstra's Algorithm in C Programming

The document contains a C program that implements Dijkstra's algorithm to find the shortest path in a graph represented by an adjacency matrix. It initializes distances, selects the unvisited vertex with the smallest distance, updates neighboring vertices, and prints the shortest distance and path from a specified starting vertex to a destination vertex. The program also includes user input for the number of vertices, the adjacency matrix, and the starting and destination vertices.

Uploaded by

Aritra Das
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd

#include <stdio.

h>
#include <limits.h>

#define MAX 100


#define INF INT_MAX

void dijkstra(int graph[MAX][MAX], int n, int start, int dest) {


int dist[MAX]; // Array to store the shortest distances
int visited[MAX] = {0}; // Visited vertices
int parent[MAX]; // To store the shortest path tree

// Initialize distances and parent array


for (int i = 0; i < n; i++) {
dist[i] = INF;
parent[i] = -1;
}
dist[start] = 0; // Distance from the starting vertex to itself is 0

// Main loop
for (int count = 0; count < n - 1; count++) {
int u = -1;

// Select the unvisited vertex with the smallest distance


for (int i = 0; i < n; i++) {
if (!visited[i] && (u == -1 || dist[i] < dist[u])) {
u = i;
}
}

// Mark the selected vertex as visited


visited[u] = 1;

// Update distances of neighboring vertices


for (int v = 0; v < n; v++) {
if (graph[u][v] != 0 && !visited[v] && dist[u] != INF && dist[u] +
graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
parent[v] = u; // Update the parent
}
}
}

// Print the shortest distance


printf("Shortest distance from vertex %d to vertex %d: %d\n", start, dest,
dist[dest]);

// Print the shortest path


printf("Shortest path: ");
int path[MAX];
int pathIndex = 0;
for (int v = dest; v != -1; v = parent[v]) {
path[pathIndex++] = v;
}
for (int i = pathIndex - 1; i >= 0; i--) {
printf("%d%s", path[i], (i > 0) ? " -> " : "\n");
}
}

int main() {
int n;
int graph[MAX][MAX];
int start, dest;

// Input number of vertices


printf("Enter the number of vertices: ");
scanf("%d", &n);

// Input adjacency matrix


printf("Enter the adjacency matrix (use 0 for no edge):\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &graph[i][j]);
}
}

// Input starting and destination vertices


printf("Enter the starting vertex (0 to %d): ", n - 1);
scanf("%d", &start);
printf("Enter the destination vertex (0 to %d): ", n - 1);
scanf("%d", &dest);

// Run Dijkstra's algorithm


dijkstra(graph, n, start, dest);

return 0;
}

You might also like