Dijkstra’s Algorithm is a graph-based algorithm used to find the shortest path from a source node to all other vertices in a weighted graph with non-negative edge weights. It is widely used in networking, route optimization, and mapping applications. Understanding Dijkstra’s Algorithm helps in solving real-world problems involving optimal paths efficiently.
Think of a map of cities and roads: each city is a vertex, and each road has a distance (weight). Dijkstra’s Algorithm is like planning the shortest travel routes from one city to every other city. Depending on how you record the map, you can use: a full distance table (adjacency matrix), a list of actual roads (adjacency list), or a smart assistant with a notebook (adjacency list + priority queue). Each version balances simplicity, memory, and speed differently.
Understanding the Problem
The main challenge in implementing Dijkstra’s Algorithm is tracking the shortest distances and ensuring each node is visited only once. We maintain an array of distances from the source and repeatedly select the unvisited vertex with the minimum distance. Then we update the distances of its neighbors, gradually finding the shortest paths.
Program 1: Dijkstra’s Algorithm (Adjacency Matrix)
This program demonstrates Dijkstra’s Algorithm using an adjacency matrix to find the shortest path from a source vertex to all other vertices.
#include <stdio.h>
#include <limits.h>
#define V 5 // Number of vertices
// Find the vertex with minimum distance
int minDistance(int dist[], int visited[]) {
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (!visited[v] && dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}
// Print distance array
void printSolution(int dist[]) {
printf("Vertex \t Distance from Source\n");
for (int i = 0; i < V; i++)
printf("%d \t %d\n", i, dist[i]);
}
// Dijkstra’s Algorithm
void dijkstra(int graph[V][V], int src) {
int dist[V], visited[V];
for (int i = 0; i < V; i++) {
dist[i] = INT_MAX;
visited[i] = 0;
}
dist[src] = 0;
for (int count = 0; count < V - 1; count++) {
int u = minDistance(dist, visited);
visited[u] = 1;
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];
}
printSolution(dist);
}
int main() {
int graph[V][V] = {
{0, 10, 0, 0, 5},
{0, 0, 1, 0, 2},
{0, 0, 0, 4, 0},
{7, 0, 6, 0, 0},
{0, 3, 9, 2, 0}
};
int source = 0;
printf("Dijkstra’s shortest path from vertex %d:\n", source);
dijkstra(graph, source);
return 0;
}This implementation selects the unvisited vertex with the smallest distance in each step. Distances of adjacent vertices are updated iteratively, and the process continues until all vertices are visited, yielding the shortest path from the source to every vertex.
Program 2: Dijkstra’s Algorithm (Adjacency List)
This version uses an adjacency list, which is memory-efficient for sparse graphs. A min-priority queue is simulated with a simple array for simplicity.
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
typedef struct Node {
int vertex;
int weight;
struct Node *next;
} Node;
typedef struct Graph {
int V;
Node **adjLists;
} Graph;
// Create adjacency node
Node* createNode(int v, int w) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->vertex = v;
newNode->weight = w;
newNode->next = NULL;
return newNode;
}
// Create graph
Graph* createGraph(int V) {
Graph *graph = (Graph*) malloc(sizeof(Graph));
graph->V = V;
graph->adjLists = (Node**)malloc(V * sizeof(Node*));
for (int i = 0; i < V; i++) graph->adjLists[i] = NULL;
return graph;
}
// Add directed edge
void addEdge(Graph *graph, int src, int dest, int weight) {
Node *newNode = createNode(dest, weight);
newNode->next = graph->adjLists[src];
graph->adjLists[src] = newNode;
}
// Find unvisited vertex with minimum distance
int minDistance(int dist[], int visited[], int V) {
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (!visited[v] && dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}
// Dijkstra’s Algorithm
void dijkstra(Graph *graph, int src) {
int V = graph->V;
int *dist = (int*) malloc(V * sizeof(int));
int *visited = (int*)malloc(V * sizeof(int));
for (int i = 0; i < V; i++) {
dist[i] = INT_MAX;
visited[i] = 0;
}
dist[src] = 0;
for (int count = 0; count < V - 1; count++) {
int u = minDistance(dist, visited, V);
visited[u] = 1;
Node *temp = graph->adjLists[u];
while (temp) {
int v = temp->vertex;
int w = temp->weight;
if (!visited[v] && dist[u] != INT_MAX && dist[u] + w < dist[v])
dist[v] = dist[u] + w;
temp = temp->next;
}
}
printf("Vertex \t Distance from Source\n");
for (int i = 0; i < V; i++) printf("%d \t %d\n", i, dist[i]);
free(dist);
free(visited);
}
int main() {
int V = 5;
Graph *graph = createGraph(V);
addEdge(graph, 0, 1, 10);
addEdge(graph, 0, 4, 5);
addEdge(graph, 1, 2, 1);
addEdge(graph, 1, 4, 2);
addEdge(graph, 2, 3, 4);
addEdge(graph, 3, 0, 7);
addEdge(graph, 3, 2, 6);
addEdge(graph, 4, 1, 3);
addEdge(graph, 4, 2, 9);
addEdge(graph, 4, 3, 2);
printf("Dijkstra’s shortest path from vertex 0:\n");
dijkstra(graph, 0);
// Free memory
for (int i = 0; i < V; i++) {
Node *temp = graph->adjLists[i];
while (temp) {
Node *toFree = temp;
temp = temp->next;
free(toFree);
}
}
free(graph->adjLists);
free(graph);
return 0;
}Using adjacency lists, Dijkstra’s algorithm efficiently processes only the existing edges. Distances are updated iteratively by relaxing each edge of the selected vertex, and unvisited vertices are tracked to ensure shortest paths are computed correctly.
Program 3: Dijkstra’s Algorithm (Adjacency List + Min-Heap Priority Queue)
This program demonstrates Dijkstra’s Algorithm using an adjacency list combined with a min-heap priority queue. This approach is the most efficient for sparse graphs because it avoids scanning all vertices linearly and instead uses a heap to quickly extract the vertex with the smallest distance.
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
// Node in adjacency list
typedef struct Node {
int vertex;
int weight;
struct Node *next;
} Node;
// Graph structure
typedef struct Graph {
int V;
Node **adjLists;
} Graph;
// Min-Heap node
typedef struct MinHeapNode {
int vertex;
int dist;
} MinHeapNode;
// Min-Heap structure
typedef struct MinHeap {
int size;
int capacity;
int *pos;
MinHeapNode **array;
} MinHeap;
// Create adjacency node
Node* createNode(int v, int w) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->vertex = v;
newNode->weight = w;
newNode->next = NULL;
return newNode;
}
// Create graph
Graph* createGraph(int V) {
Graph *graph = (Graph*) malloc(sizeof(Graph));
graph->V = V;
graph->adjLists = (Node**) malloc(V * sizeof(Node*));
for (int i = 0; i < V; i++) graph->adjLists[i] = NULL;
return graph;
}
// Add directed edge
void addEdge(Graph *graph, int src, int dest, int weight) {
Node *newNode = createNode(dest, weight);
newNode->next = graph->adjLists[src];
graph->adjLists[src] = newNode;
}
// Create MinHeap node
MinHeapNode* newMinHeapNode(int v, int dist) {
MinHeapNode *node = (MinHeapNode*) malloc(sizeof(MinHeapNode));
node->vertex = v;
node->dist = dist;
return node;
}
// Create MinHeap
MinHeap* createMinHeap(int capacity) {
MinHeap *minHeap = (MinHeap*) malloc(sizeof(MinHeap));
minHeap->pos = (int*) malloc(capacity * sizeof(int));
minHeap->size = 0;
minHeap->capacity = capacity;
minHeap->array = (MinHeapNode**) malloc(capacity * sizeof(MinHeapNode*));
return minHeap;
}
// Swap two MinHeap nodes
void swapMinHeapNode(MinHeapNode **a, MinHeapNode **b) {
MinHeapNode *t = *a;
*a = *b;
*b = t;
}
// Heapify at index
void minHeapify(MinHeap *minHeap, int idx) {
int smallest = idx;
int left = 2 * idx + 1;
int right = 2 * idx + 2;
if (left < minHeap->size &&
minHeap->array[left]->dist < minHeap->array[smallest]->dist)
smallest = left;
if (right < minHeap->size &&
minHeap->array[right]->dist < minHeap->array[smallest]->dist)
smallest = right;
if (smallest != idx) {
MinHeapNode *smallestNode = minHeap->array[smallest];
MinHeapNode *idxNode = minHeap->array[idx];
minHeap->pos[smallestNode->vertex] = idx;
minHeap->pos[idxNode->vertex] = smallest;
swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]);
minHeapify(minHeap, smallest);
}
}
// Check if heap is empty
int isEmpty(MinHeap *minHeap) {
return minHeap->size == 0;
}
// Extract min node
MinHeapNode* extractMin(MinHeap *minHeap) {
if (isEmpty(minHeap)) return NULL;
MinHeapNode *root = minHeap->array[0];
MinHeapNode *lastNode = minHeap->array[minHeap->size - 1];
minHeap->array[0] = lastNode;
minHeap->pos[root->vertex] = minHeap->size - 1;
minHeap->pos[lastNode->vertex] = 0;
minHeap->size--;
minHeapify(minHeap, 0);
return root;
}
// Decrease key (update distance)
void decreaseKey(MinHeap *minHeap, int v, int dist) {
int i = minHeap->pos[v];
minHeap->array[i]->dist = dist;
while (i && minHeap->array[i]->dist < minHeap->array[(i - 1) / 2]->dist) {
minHeap->pos[minHeap->array[i]->vertex] = (i - 1) / 2;
minHeap->pos[minHeap->array[(i - 1) / 2]->vertex] = i;
swapMinHeapNode(&minHeap->array[i], &minHeap->array[(i - 1) / 2]);
i = (i - 1) / 2;
}
}
// Check if vertex is in heap
int isInMinHeap(MinHeap *minHeap, int v) {
return minHeap->pos[v] < minHeap->size;
}
// Dijkstra’s Algorithm with MinHeap
void dijkstra(Graph *graph, int src) {
int V = graph->V;
int dist[V];
MinHeap *minHeap = createMinHeap(V);
for (int v = 0; v < V; v++) {
dist[v] = INT_MAX;
minHeap->array[v] = newMinHeapNode(v, dist[v]);
minHeap->pos[v] = v;
}
dist[src] = 0;
decreaseKey(minHeap, src, dist[src]);
minHeap->size = V;
while (!isEmpty(minHeap)) {
MinHeapNode *minHeapNode = extractMin(minHeap);
int u = minHeapNode->vertex;
Node *pCrawl = graph->adjLists[u];
while (pCrawl != NULL) {
int v = pCrawl->vertex;
if (isInMinHeap(minHeap, v) &&
dist[u] != INT_MAX &&
pCrawl->weight + dist[u] < dist[v]) {
dist[v] = dist[u] + pCrawl->weight;
decreaseKey(minHeap, v, dist[v]);
}
pCrawl = pCrawl->next;
}
}
printf("Vertex \t Distance from Source\n");
for (int i = 0; i < V; i++) printf("%d \t %d\n", i, dist[i]);
}
// Main
int main() {
int V = 5;
Graph *graph = createGraph(V);
addEdge(graph, 0, 1, 10);
addEdge(graph, 0, 4, 5);
addEdge(graph, 1, 2, 1);
addEdge(graph, 1, 4, 2);
addEdge(graph, 2, 3, 4);
addEdge(graph, 3, 0, 7);
addEdge(graph, 3, 2, 6);
addEdge(graph, 4, 1, 3);
addEdge(graph, 4, 2, 9);
addEdge(graph, 4, 3, 2);
printf("Dijkstra’s shortest path from vertex 0:\n");
dijkstra(graph, 0);
return 0;
}This implementation leverages a min-heap priority queue to extract the vertex with the smallest distance efficiently in O(log V) time. By pairing this with an adjacency list, the algorithm only processes existing edges, making it highly suitable for large and sparse graphs. This is the most practical and commonly used version of Dijkstra’s algorithm in real-world applications.
Comparison of Dijkstra’s Algorithm Implementations
Each version of Dijkstra’s Algorithm has different trade-offs depending on graph size and density. The choice of data structure for graph representation and vertex selection impacts both time complexity and space usage.
| Program | Graph Representation | Vertex Selection | Time Complexity | Space Complexity | Best For |
|---|---|---|---|---|---|
| Program 1 | Adjacency Matrix | Linear Search | O(V²) | O(V²) | Dense graphs |
| Program 2 | Adjacency List | Linear Search | O(V²) | O(V + E) | Small or moderately sparse graphs |
| Program 3 | Adjacency List | Min-Heap (Priority Queue) | O((V + E) log V) | O(V + E) | Large sparse graphs |
In summary, Program 1 is straightforward but inefficient for large graphs since it always checks all vertices. Program 2 improves memory usage by only storing existing edges but still uses linear search for vertex selection. Program 3 combines adjacency lists with a min-heap, making it the most efficient choice for sparse graphs and widely used in practice.
FAQs
Q1: What is the time complexity of Dijkstra’s Algorithm?
With an adjacency matrix, the time complexity is O(V²). Using an adjacency list with a priority queue (min-heap) makes it much faster, running in O((V + E) log V), which is better for large sparse graphs.
Q2: Can Dijkstra’s Algorithm handle negative weights?
No, it cannot handle negative edge weights, because the algorithm assumes that once a vertex is visited with the shortest distance, it will not be improved further. For negative edges, algorithms like Bellman-Ford are used instead.
Q3: Is Dijkstra’s Algorithm greedy?
Yes. It follows a greedy approach by always choosing the vertex with the current shortest known distance to expand next.
Q4: Can it find paths to all vertices?
Yes. Starting from a single source, it computes the shortest path to every other vertex in the graph, building a complete shortest-path tree.
Conclusion
Dijkstra’s Algorithm is one of the most important algorithms for shortest path problems in weighted graphs with non-negative edges. Its efficiency depends on how the graph and priority selection are implemented—ranging from simple matrix forms to advanced heap-based methods.
By mastering Dijkstra’s Algorithm, you gain the foundation for solving real-world challenges like network routing, GPS navigation, and logistics planning, where finding the quickest and most efficient routes is essential.
In modern life, Dijkstra’s ideas power applications such as Google Maps, which calculates driving routes, and internet packet routing, where data must travel through the fastest and most reliable paths. From airline scheduling to supply chain optimization, this algorithm continues to be a cornerstone of efficient planning and problem-solving.
References & Additional Resources
These books and online resources provide both theoretical explanations and practical examples for understanding Dijkstra’s algorithm and related graph algorithms in C.
- Kernighan, Brian W., and Dennis M. Ritchie. The C Programming Language. 2nd Edition, Prentice Hall, 1988.
- Thareja, R. (2011). Data Structures Using C. Oxford University Press – Covers fundamental graph concepts, shortest path algorithms, and their implementation in C.
- GeeksforGeeks: Dijkstra’s Algorithm – Step-by-step explanation and C implementation of Dijkstra’s shortest path algorithm.
