Exploring Dijkstra’s Algorithm in C: A Step-by-Step Guide

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.

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!

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top