Dijkstra's Algorithm
Dijkstra's algorithm finds the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights.
Introduction
Dijkstra's Algorithm, developed by Edsger Dijkstra in 1956, solves the Single Source Shortest Path (SSSP) problem for graphs with non-negative edge weights. It is one of the most famous and widely used algorithms in computer science, powering GPS navigation, network routing protocols, and many more applications.
Problem Statement
Given a weighted directed or undirected graph G = (V, E) with non-negative edge weights and a source vertex s, find the shortest path distance from s to every other vertex in the graph.
Real World Applications
- → GPS navigation — finding shortest driving route
- → Network routing protocols (OSPF uses Dijkstra's)
- → Airline flight path optimization
- → Social network shortest connection finder
- → Robot path planning
Algorithm Explanation
Dijkstra's maintains a distance array dist[] initialized to INFI (infinity) except dist[source] = 0. It repeatedly selects the unvisited vertex u with minimum dist[u], marks it visited, and relaxes all edges from u — if dist[u] + weight(u,v) < dist[v], update dist[v]. This greedy selection guarantees correctness for non-negative weights.
Step-by-Step Procedure
- 1 Initialize dist[source] = 0 and dist[all others] = INFI (99). Mark all vertices unvisited.
- 2 Set dist[i] = weight[source][i] for direct neighbors.
- 3 Pick the unvisited vertex u with minimum dist[u] using Minvertex().
- 4 Mark u as visited.
- 5 For each unvisited neighbor j of u: if dist[u] + weight[u][j] < dist[j], update dist[j] = dist[u] + weight[u][j] and set p[j] = u (parent).
- 6 Repeat steps 3-5 for all vertices.
- 7 Print shortest distances and paths using the parent array p[].
Complete C Program
#include<stdio.h>
#include<stdlib.h>
#define INFI 99
int dist[10], p[10], visit[10];
int wt[10][10], n;
int Minvertex() {
int i, u, min = INFI;
for(i = 1; i <= n; i++) {
if(dist[i] < min && visit[i] == 0) {
min = dist[i];
u = i;
}
}
return u;
}
void dijkstra(int s) {
int i, j, step, u;
for(i = 1; i <= n; i++) {
dist[i] = wt[s][i];
p[i] = (dist[i] == INFI) ? 0 : s;
}
visit[s] = 1;
dist[s] = 0;
for(step = 0; step <= n; step++) {
u = Minvertex();
visit[u] = 1;
for(j = 1; j <= n; j++) {
if((dist[u] + wt[u][j]) < dist[j] && !visit[j]) {
dist[j] = wt[u][j] + dist[u];
p[j] = u;
}
}
}
}
void printpath(int s) {
int i, t;
for(i = 1; i <= n; i++) {
if(visit[i] == 1 && i != s) {
printf("Vertex %d: length %d, path: %d", i, dist[i], i);
t = p[i];
while(t != s) {
printf(" <--- %d", t);
t = p[t];
}
printf(" <--- %d\n", s);
}
}
}
int main() {
int i, j, s;
printf("Enter the number of vertices: ");
scanf("%d", &n);
printf("Enter the Distance Matrix:\n");
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
scanf("%d", &wt[i][j]);
printf("Enter Source Vertex: ");
scanf("%d", &s);
dijkstra(s);
printf("\nShortest paths from vertex %d:\n", s);
printpath(s);
return 0;
}Sample Input & Output
4
99 3 99 7
3 99 2 99
99 2 99 1
7 99 1 99
1Shortest paths from vertex 1:
Vertex 2: length 3, path: 2 <--- 1
Vertex 3: length 5, path: 3 <--- 2 <--- 1
Vertex 4: length 6, path: 4 <--- 3 <--- 2 <--- 1Dry Run / Trace
Source = 1. dist = [0, 3, 99, 7] Step 1: Pick vertex 2 (dist=3). Relax: dist[3] = 3+2=5, dist[4] unchanged. Step 2: Pick vertex 3 (dist=5). Relax: dist[4] = min(7, 5+1)=6. Step 3: Pick vertex 4 (dist=6). All vertices visited. Result: dist = [0, 3, 5, 6]
Advantages & Disadvantages
✓ Advantages
- + Finds shortest paths from a single source to all vertices
- + Optimal for graphs with non-negative weights
- + Forms the basis of many network routing algorithms
- + Easy to implement with adjacency matrix
✗ Disadvantages
- − Does not work with negative edge weights
- − O(V²) with adjacency matrix — can be improved to O(E log V) with priority queue
- − Only finds single-source shortest paths (not all-pairs)
Viva Questions & Answers
Q1. Why does Dijkstra's algorithm not work with negative edge weights?
The greedy assumption that once a vertex is visited its distance is final breaks down with negative weights. Bellman-Ford should be used instead.
Q2. What is the time complexity of Dijkstra's with a min-heap?
O(E log V) using a binary min-heap or O(E + V log V) using a Fibonacci heap.
Q3. What is edge relaxation in Dijkstra's algorithm?
Checking if the path to vertex v through u (dist[u] + weight[u][v]) is shorter than the current known distance dist[v]. If so, updating dist[v].
Q4. How is Dijkstra's different from BFS?
BFS finds shortest paths in unweighted graphs. Dijkstra's handles weighted graphs by using a priority queue instead of a simple queue.
Q5. What is the role of the visited array in Dijkstra's?
Once a vertex is marked visited (finalized), its shortest distance is confirmed and it won't be updated again.