Dijkstra’s algorithm is a fundamental graph traversal algorithm used to find the shortest path from a source node to all other nodes in a weighted graph. Named after its inventor, Dutch computer scientist Edsger W. Dijkstra, this algorithm is widely employed in various applications, including network routing protocols, GPS navigation systems, and task scheduling algorithms.
In this comprehensive guide, we’ll delve deep into the workings of Dijkstra’s algorithm, its implementation in C, and explore practical examples to solidify our understanding.
You may like to read about the heap data structure in C.
Understanding Dijkstra’s Algorithm
Dijkstra’s algorithm operates on a weighted graph, where each edge has a non-negative weight representing the cost or distance between two vertices.
Join my newsletter in order to gain access to cutting-edge research and developments along with free revision guides and exercises.
The algorithm maintains a set of vertices whose shortest distance from the source node is known and continuously expands this set until all vertices are included. At each step, it selects the vertex with the smallest tentative distance and updates the distances of its neighboring vertices if a shorter path is found.
Implementation in C
To implement Dijkstra’s algorithm in C, we’ll need to represent the graph and maintain data structures to track distances and visited vertices. Let’s start by defining the necessary structures and functions.
Graph Representation
We can represent the graph using an adjacency list or adjacency matrix. Here, we’ll use an adjacency list, which is more efficient for sparse graphs.
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_VERTICES 100
// Structure to represent an edge in the graph
struct Edge {
int destination;
int weight;
struct Edge* next;
};
// Structure to represent a vertex in the graph
struct Vertex {
struct Edge* head;
};
// Structure to represent the graph
struct Graph {
int numVertices;
struct Vertex vertices[MAX_VERTICES];
};Dijkstra’s Algorithm Function
void dijkstra(struct Graph* graph, int source) {
int distances[MAX_VERTICES]; // Array to store shortest distances
int visited[MAX_VERTICES]; // Array to track visited vertices
// Initialize distances and visited arrays
for (int i = 0; i < graph->numVertices; ++i) {
distances[i] = INT_MAX;
visited[i] = 0;
}
// Distance from source to itself is 0
distances[source] = 0;
// Main loop
for (int count = 0; count < graph->numVertices - 1; ++count) {
// Find the vertex with the minimum distance
int minDistance = INT_MAX;
int minIndex = -1;
for (int v = 0; v < graph->numVertices; ++v) {
if (!visited[v] && distances[v] < minDistance) {
minDistance = distances[v];
minIndex = v;
}
}
// Mark the selected vertex as visited
visited[minIndex] = 1;
// Update distances of adjacent vertices
struct Edge* edge = graph->vertices[minIndex].head;
while (edge != NULL) {
int destination = edge->destination;
if (!visited[destination] && distances[minIndex] != INT_MAX &&
distances[minIndex] + edge->weight < distances[destination]) {
distances[destination] = distances[minIndex] + edge->weight;
}
edge = edge->next;
}
}
// Print shortest distances from source
printf("Shortest distances from source %d:\n", source);
for (int i = 0; i < graph->numVertices; ++i) {
printf("Vertex %d: Distance = %d\n", i, distances[i]);
}
}Practical Example
Let’s apply Dijkstra’s algorithm to find the shortest paths from a source node to all other nodes in a sample graph.
int main() {
struct Graph graph;
graph.numVertices = 6;
// Add edges to the graph
addEdge(&graph, 0, 1, 4);
addEdge(&graph, 0, 2, 1);
addEdge(&graph, 1, 2, 2);
addEdge(&graph, 1, 3, 5);
addEdge(&graph, 2, 3, 2);
addEdge(&graph, 2, 4, 4);
addEdge(&graph, 3, 4, 1);
addEdge(&graph, 3, 5, 5);
addEdge(&graph, 4, 5, 2);
// Perform Dijkstra's algorithm
int source = 0;
dijkstra(&graph, source);
return 0;
}Conclusion
In this comprehensive guide, we’ve explored Dijkstra’s algorithm, its implementation in C, and a practical example demonstrating its usage. Dijkstra’s algorithm is a powerful tool for finding shortest paths in weighted graphs and has numerous applications in computer science and beyond.
Understanding its principles and implementation details is essential for any programmer aspiring to tackle graph-related problems effectively. With the knowledge gained from this guide, you’re well-equipped to utilize Dijkstra’s algorithm in your C programming endeavors.
Happy coding!
