Mastering Dijkstra’s Algorithm in C: Step-by-Step Guide with Code and Examples

person using silver macbook pro

Here’s a simplified implementation of Dijkstra’s Algorithm in C. This code assumes that the graph is represented using an adjacency matrix and uses arrays to store distance and visited information. Note that this code is for educational purposes and may require modifications for specific use cases.

#include <stdio.h>
#include <stdbool.h>

#define V 6  // Number of vertices in the graph

// Function to find the vertex with the minimum distance value
int minDistance(int dist[], bool 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;
}

// Function to print the shortest path from source to destination
void printPath(int parent[], int j) {
    if (parent[j] == -1)
        return;

    printPath(parent, parent[j]);
    printf(" -> %d", j);
}

// Function to print the final result, including shortest paths and distances
void printSolution(int dist[], int parent[], int src) {
    printf("Vertex   Distance from Source   Shortest Path\n");
    for (int i = 0; i < V; i++) {
        if (i == src)
            continue;

        printf("%d -> %d       %d                %d", src, i, dist[i], src);
        printPath(parent, i);
        printf("\n");
    }
}

// Function to perform Dijkstra's Algorithm
void dijkstra(int graph[V][V], int src) {
    int dist[V];        // Array to store the shortest distances from the source vertex
    bool visited[V];    // Array to track visited vertices
    int parent[V];      // Array to store the parent vertices in the shortest path tree

    // Initialize arrays
    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
        visited[i] = false;
        parent[i] = -1;
    }

    // Distance of the source vertex from itself is always 0
    dist[src] = 0;

    // Find shortest path for all vertices
    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, visited);
        visited[u] = true;

        // Update dist[] values of adjacent vertices
        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];
                parent[v] = u;
            }
        }
    }

    // Print the result
    printSolution(dist, parent, src);
}

int main() {
    int graph[V][V] = {
        {0, 4, 0, 0, 0, 0},
        {4, 0, 8, 0, 0, 0},
        {0, 8, 0, 7, 0, 4},
        {0, 0, 7, 0, 9, 14},
        {0, 0, 0, 9, 0, 10},
        {0, 0, 4, 14, 10, 0}
    };

    int source = 0;  // Source vertex
    dijkstra(graph, source);

    return 0;
}

This code defines the Dijkstra’s Algorithm for finding the shortest path in a weighted graph. It uses an adjacency matrix to represent the graph and calculates the shortest paths and distances from a specified source vertex. The result is printed, including the shortest paths and distances from the source vertex to all other vertices in the graph.

Let’s break down the code for Dijkstra’s Algorithm in C step by step

#include <stdio.h>
#include <stdbool.h>

#define V 6  // Number of vertices in the graph
  • The code begins by including necessary headers: <stdio.h> for standard input/output and <stdbool.h> for using the bool data type.
  • It defines V as the number of vertices in the graph. In this example, we have a graph with 6 vertices.
// Function to find the vertex with the minimum distance value
int minDistance(int dist[], bool 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;
}
  • minDistance is a helper function to find the vertex with the minimum distance value among the vertices that haven’t been visited.
  • It takes two arrays as input: dist[], which stores the distances from the source vertex, and visited[], which tracks visited vertices.
  • The function initializes min to a very large value (INT_MAX) and min_index to -1.
  • It iterates through all vertices, checks if they haven’t been visited and if their distance is smaller than the current minimum distance.
  • If a smaller distance is found, min and min_index are updated.
// Function to print the shortest path from source to destination
void printPath(int parent[], int j) {
    if (parent[j] == -1)
        return;

    printPath(parent, parent[j]);
    printf(" -> %d", j);
}
  • printPath is a recursive function to print the shortest path from the source vertex to a given destination vertex j.
  • It uses an array parent[] to trace back the path by recursively calling itself until it reaches the source vertex.
  • The path is printed in the format “source -> … -> destination”.
// Function to print the final result, including shortest paths and distances
void printSolution(int dist[], int parent[], int src) {
    printf("Vertex   Distance from Source   Shortest Path\n");
    for (int i = 0; i < V; i++) {
        if (i == src)
            continue;

        printf("%d -> %d       %d                %d", src, i, dist[i], src);
        printPath(parent, i);
        printf("\n");
    }
}
  • printSolution is a function to print the final result, including the shortest paths and distances from the source vertex to all other vertices.
  • It uses the dist[] array to print distances and calls printPath to print the shortest paths.
  • The output is formatted as a table with columns for the vertex, distance from the source, and the shortest path.
// Function to perform Dijkstra's Algorithm
void dijkstra(int graph[V][V], int src) {
    int dist[V];        // Array to store the shortest distances from the source vertex
    bool visited[V];    // Array to track visited vertices
    int parent[V];      // Array to store the parent vertices in the shortest path tree

    // Initialize arrays
    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
        visited[i] = false;
        parent[i] = -1;
    }

    // Distance of the source vertex from itself is always 0
    dist[src] = 0;

    // Find shortest path for all vertices
    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, visited);
        visited[u] = true;

        // Update dist[] values of adjacent vertices
        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];
                parent[v] = u;
            }
        }
    }

    // Print the result
    printSolution(dist, parent, src);
}
  • The dijkstra function performs the core Dijkstra’s Algorithm.
  • It initializes arrays for distances (dist[]), visited vertices (visited[]), and parent vertices (parent[]).
  • The distance from the source vertex to itself is set to 0, and all other distances are initialized to INT_MAX.
  • The algorithm iterates V - 1 times (where V is the number of vertices) to find the shortest path for all vertices.
  • In each iteration, it selects the vertex u with the minimum distance using minDistance and marks it as visited.
  • It then updates the distances to adjacent vertices if a shorter path is found and updates the parent vertices.
  • Finally, it calls printSolution to print the result.
int main() {
    int graph[V][V] = {
        {0, 4, 0, 0, 0, 0},
        {4, 0, 8, 0, 0, 0},
        {0, 8, 0, 7, 0, 4},
        {0, 0, 7, 0, 9, 14},
        {0, 0, 0, 9, 0, 10},
        {0, 0, 4, 14, 10, 0}
    };

    int source = 0;  // Source vertex
    dijkstra(graph, source);

    return 0;
}
  • In the main function, a sample graph represented as an adjacency matrix is defined.
  • The source vertex is set to 0 (in this example).
  • The dijkstra function is called with the graph and source vertex as arguments, which then prints the result, including the shortest paths and distances.

1. Understanding Dijkstra’s Algorithm:

  • Dijkstra’s Algorithm is a widely used algorithm for finding the shortest path in a weighted graph. It was developed by computer scientist Edsger W. Dijkstra.
  • The core idea is to iteratively select the nearest unvisited vertex and update the distances to its neighbors if a shorter path is found.
  • Dijkstra’s Algorithm works with both directed and undirected graphs and assumes non-negative edge weights.
  • It guarantees the shortest path from a source vertex to all other vertices in the graph.

2. The Graph Data Structure:

  • Graphs can be represented in C using either adjacency matrices or adjacency lists.
  • An adjacency matrix is a 2D array where matrix[i][j] represents the weight of the edge between vertices i and j. It’s suitable for dense graphs but consumes more memory.
  • Adjacency lists use arrays or linked lists to represent neighbors for each vertex. They are more memory-efficient for sparse graphs.
  • The choice of data structure depends on the specific problem and available memory.

3. Priority Queue Implementation:

  • Priority queues are essential for efficiently selecting the next vertex with the shortest distance.
  • In C, you can implement a priority queue using arrays, linked lists, or binary heaps.
  • Binary heaps are a popular choice due to their efficient operations for insertion, deletion, and retrieval of the minimum element.
  • Libraries like <stdio.h> provide basic functions for building priority queues.

4. Algorithm Walkthrough:

  • Dijkstra’s Algorithm starts by initializing all distances to infinity except for the source vertex, which is set to 0.
  • It then repeatedly selects the vertex with the smallest distance, updates the distances to its neighbors if a shorter path is found, and marks it as visited.
  • The process continues until all vertices are visited or the target vertex is reached.
  • Below is an example of a graph and its application of Dijkstra’s Algorithm:

5. Dijkstra’s Algorithm in C:

  • Implementing Dijkstra’s Algorithm in C involves defining data structures for vertices, edges, and priority queues.
  • You’ll need functions to initialize data structures, perform edge relaxations, and execute the algorithm.

6. Handling Negative Weights and Cycles:

  • Dijkstra’s Algorithm assumes non-negative edge weights. Negative weights can lead to incorrect results or infinite loops.
  • To handle negative edge weights, consider using algorithms like Bellman-Ford.
  • Negative-weight cycles can cause Dijkstra’s Algorithm to fail, so it’s important to detect and handle them properly.

7. Applications of Dijkstra’s Algorithm:

  • Dijkstra’s Algorithm has a wide range of real-world applications, including:
    • GPS navigation to find the shortest route.
    • Network routing to determine optimal paths for data transmission.
    • Game pathfinding for characters or objects.
  • In each case, Dijkstra’s Algorithm efficiently finds the shortest path between two points.

8. Optimization Techniques:

  • To optimize Dijkstra’s Algorithm, consider techniques like:
    • Bidirectional search, where the algorithm runs simultaneously from both the source and target vertices.
    • A* search, which combines Dijkstra’s Algorithm with heuristics to improve efficiency.

9. Comparing Dijkstra’s Algorithm with Other Pathfinding Algorithms:

  • Dijkstra’s Algorithm guarantees the shortest path but can be slower for large graphs.
  • Breadth-First Search is simpler and can find the shortest path in unweighted graphs.
  • A* search combines Dijkstra’s approach with heuristics for faster results, making it suitable for games and maps.

10. Error Handling and Robustness:

Robust implementations of Dijkstra’s Algorithm should handle errors gracefully, such as cases where vertices are unreachable or input data is missing. – Implementing checks for these edge cases ensures the algorithm works reliably in practical scenarios.

In conclusion, Dijkstra’s Algorithm is a powerful tool for solving shortest path problems in graphs. By understanding its principles, implementing it in C, and considering its applications and limitations, you’ll be well-equipped to apply this algorithm effectively in various contexts.

Scroll to Top