Dijkstrs's Algorithm
Published by: Anil K. Panta
Dijkstra’s Algorithm | Shortest Path Using Greedy Approach
Dijkstra’s Algorithm is a famous Greedy Algorithm used to find the shortest path from a single source vertex to all other vertices in a weighted graph (with non-negative weights).
Why Use Dijkstra’s Algorithm?
Finds the shortest path from a single source to all other nodes.
Works on both directed and undirected graphs.
Efficient for routing, GPS systems, and network optimization.
Key Concepts
How Dijkstra’s Algorithm Works (Step-by-Step)
Set all distances to ∞, except the source node which is set to 0.
Mark all nodes as unvisited.
From the current node, visit its unvisited neighbors.
Update their distances if the new path is shorter.
Mark the current node as visited.
Repeat until all nodes are visited.
Dijkstra’s Algorithm in C
#include <stdio.h>
#include <limits.h>
#include <stdbool.h>
#define V 6 // Total number of vertices
// Function to find the vertex with minimum distance
int min_dist(int dist[], bool visited[]) {
int min = INT_MAX, index;
for (int i = 0; i < V; i++) {
if (!visited[i] && dist[i] <= min) {
min = dist[i];
index = i;
}
}
return index;
}
// Dijkstra’s Algorithm Implementation
void greedy_dijkstra(int graph[V][V], int src) {
int dist[V];
bool visited[V];
// Step 1: Initialize distances and visited array
for (int i = 0; i < V; i++) {
dist[i] = INT_MAX;
visited[i] = false;
}
dist[src] = 0; // Distance of source from itself is always 0
// Step 2: Visit each vertex
for (int i = 0; i < V - 1; i++) {
int u = min_dist(dist, visited);
visited[u] = true;
// Step 3: Update distances of neighbors
for (int v = 0; v < V; 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];
}
}
}
// Step 4: Print final distances
printf("Vertex\t\tDistance from Source\n");
for (int i = 0; i < V; i++) {
printf("%c\t\t%d\n", 'A' + i, dist[i]);
}
}
int main() {
int graph[V][V] = {
{0, 1, 2, 0, 0, 0},
{1, 0, 0, 5, 1, 0},
{2, 0, 0, 2, 3, 0},
{0, 5, 2, 0, 2, 2},
{0, 1, 3, 2, 0, 1},
{0, 0, 0, 2, 1, 0}
};
greedy_dijkstra(graph, 0); // Starting from vertex A
return 0;
}
Output:
Vertex Distance from Source
A 0
B 1
C 2
D 4
E 2
F 3
Time and Space Complexity
Advantages
Simple and easy to implement
Efficient for small or medium-sized graphs
Limitations
Does not work with negative edge weights
Slower on very large graphs (use optimized version with priority queue)
Real-World Applications
Google Maps, GPS navigation
Packet routing in networks
Game AI pathfinding
Robotics motion planning
Summary Table
Final Thought
Dijkstra’s Algorithm gives you the most efficient route — whether you're sending data, planning delivery routes, or guiding a robot through a maze.
