Dijkstra’s Algorithm
Aim:
From a given vertex in a weighted connected graph, develop a program to
find the shortest path to other vertices using the Dijkstra's algorithm .
Algorithm:
1. Input the graph:
o Read the number of vertices.
o Input the weighted adjacency matrix of the graph.
2. Initialization:
o Create an array dist[] to store the minimum distance from the source to each
vertex.
o Create a boolean array visited[] to track processed vertices.
o Set all distances to infinity (INF) except the source vertex, which is set to 0.
3. Processing Vertices:
o For each vertex not yet processed:
● Find the vertex u with the minimum distance that hasn't been
processed.
● Mark u as processed.
● Update the distance for all adjacent vertices of u that haven't been
processed yet.
4. Update Distance:
o If the path through vertex u provides a shorter path to vertex v, update dist[v].
5. Repeat until all vertices are processed.
6. Output the shortest distances from the source to all vertices.
Program:
#include <stdio.h>
#include <limits.h>
#define MAX 100
#define INF INT_MAX
// Function to find the vertex with minimum distance
int minDistance(int dist[], int visited[], int n) {
int min = INF, min_index;
for (int v = 0; v < n; v++)
if (visited[v] == 0 && dist[v] <= min) {
min = dist[v];
min_index = v;
}
return min_index;
}
// Implementation of Dijkstra's algorithm
void dijkstra(int graph[MAX][MAX], int n, int src) {
int dist[MAX]; // Shortest distances from src
int visited[MAX]; // To track visited vertices
// Initialize all distances to INF and visited[] to false
for (int i = 0; i < n; i++) {
dist[i] = INF;
visited[i] = 0;
}
dist[src] = 0; // Distance of source vertex to itself is always 0
// Loop to find the shortest path for all vertices
for (int count = 0; count < n - 1; count++) {
int u = minDistance(dist, visited, n); // Get the vertex with the minimum distance
visited[u] = 1; // Mark the picked vertex as visited
// Update the distance value of the adjacent vertices
for (int v = 0; v < n; v++) {
if (!visited[v] && graph[u][v] && dist[u] != INF &&
dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
// Display the result
printf("\nVertex \t Distance from Source %d\n", src);
for (int i = 0; i < n; i++)
printf("%d \t\t %d\n", i, dist[i]);
}
int main() {
int n, src;
int graph[MAX][MAX];
printf("Enter the number of vertices: ");
scanf("%d", &n);
printf("Enter the weighted adjacency matrix (use 0 for no direct edge):\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &graph[i][j]);
if (i == j) // Distance to self is 0
graph[i][j] = 0;
else if (graph[i][j] == 0) // No edge present
graph[i][j] = INF;
}
}
printf("Enter the source vertex: ");
scanf("%d", &src);
dijkstra(graph, n, src);
return 0;
}
Output:
Enter the number of vertices: 4
Enter the weighted adjacency matrix (use 0 for no direct edge):
0 1 4 0
1 0 4 2
4 4 0 3
0 2 3 0
Enter the source vertex: 0
Vertex Distance from Source 0
0 0
1 1
2 4
3 3
Result:
Dijkstras algorithm was successfully implemented and
executed.
