Dijkstra’s Algorithm in C: Find the Shortest Path in Graphs

Dijkstra’s Algorithm in C: Find the Shortest Path in Graphs

Learn how to implement Dijkstra’s algorithm in C for finding the shortest path in a graph. Follow detailed code examples and explanations to master this fundamental algorithm.

Dijkstra’s algorithm is a cornerstone of graph theory and is widely used for finding the shortest path between nodes in a weighted graph. In this blog, we will explore how to implement Dijkstra’s algorithm in C, providing detailed explanations and a practical code example to help you understand this essential algorithm.

Implementing Dijkstra’s Algorithm in C

Dijkstra’s algorithm works by iteratively selecting the node with the smallest tentative distance, updating the distances to its neighboring nodes, and marking it as visited. This process continues until all nodes have been visited or the shortest path to the desired node is found.

Here’s the code snippet for implementing Dijkstra’s algorithm in C:

#include<stdio.h>
#include<conio.h>
#define INFINITY 9999
#define MAX 50

void dijkstra(int G[MAX][MAX], int n, int startnode);

int main() {
    int G[MAX][MAX], i, j, n, u, flag = 0;

    printf("Graph: Shortest Path to Other Vertices: Dijkstra Algorithm >>\n\n");
    printf("Enter Number of Vertices Present in the Graph: ");
    scanf("%d", &n);

    printf("\nEnter the Adjacency Matrix:\n");
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            scanf("%d", &G[i][j]);

    printf("\nEnter The Starting Node: ");
    scanf("%d", &u);

    printf("\nSo, The Adjacency Matrix is:\n");
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            printf("%d ", G[i][j]);
        }
        printf("\n");
    }

    dijkstra(G, n, u);

    do {
        printf("\nWant to Continue…. 1 for Yes, 0 for No : ");
        scanf("%d", &flag);
        if (flag == 1) {
            printf("\n\nEnter The Starting Node: ");
            scanf("%d", &u);
            dijkstra(G, n, u);
        }
    } while (flag == 1);

    return 0;
}

void dijkstra(int G[MAX][MAX], int n, int startnode) {
    int cost[MAX][MAX], distance[MAX], pred[MAX];
    int visited[MAX], count, mindistance, nextnode, i, j;

    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            if (G[i][j] == 0)
                cost[i][j] = INFINITY;
            else
                cost[i][j] = G[i][j];

    for (i = 0; i < n; i++) {
        distance[i] = cost[startnode][i];
        pred[i] = startnode;
        visited[i] = 0;
    }

    distance[startnode] = 0;
    visited[startnode] = 1;
    count = 1;

    while (count < n - 1) {
        mindistance = INFINITY;
        for (i = 0; i < n; i++)
            if (distance[i] < mindistance && !visited[i]) {
                mindistance = distance[i];
                nextnode = i;
            }

        visited[nextnode] = 1;
        for (i = 0; i < n; i++)
            if (!visited[i])
                if (mindistance + cost[nextnode][i] < distance[i]) {
                    distance[i] = mindistance + cost[nextnode][i];
                    pred[i] = nextnode;
                }
        count++;
    }

    for (i = 0; i < n; i++) {
        if (i != startnode) {
            if (distance[i] == 9999) {
                printf("\nThere is no Possible Path Between %d and %d.", i, startnode);
            } else {
                printf("\nDistance of Node %d to %d is: %d", i, startnode, distance[i]);
                printf("\nAnd the Path is: %d ", i);
                j = i;
                do {
                    j = pred[j];
                    printf(" -> %d", j);
                } while (j != startnode);
            }
        }
        printf("\n");
    }
}

Explanation:

1. Variable Initialization: Define the maximum number of vertices, the adjacency matrix `G`, and other variables required for the algorithm.
2. User Input: Prompt the user to enter the number of vertices, the adjacency matrix, and the starting node.
3. Cost Matrix Setup: Convert the adjacency matrix to a cost matrix, where `INFINITY` represents no direct path.
4. Initialization: Initialize the distance from the start node to all other nodes, predecessor nodes, and visited nodes.
5. Main Algorithm Loop:
— Find the node with the minimum distance that hasn’t been visited.
— Update the distances to neighboring nodes.
— Mark the node as visited and repeat until all nodes are visited.
6. Output Result: Print the shortest distance from the start node to each other node and the corresponding path.

Conclusion

Dijkstra’s algorithm is an essential tool for finding the shortest paths in weighted graphs. By understanding and implementing this algorithm in C, you can improve your skills in graph theory and algorithm analysis. This knowledge is crucial for tackling more complex problems and optimizing your code for better performance. Happy coding!

Comments

Post a Comment

Popular posts from this blog

Vue.js

Image
  Introduction to Vue.js Vue  is a  progressive framework  for building user interfaces. Unlike other monolithic frameworks, Vue is designed from the ground up to be incrementally adoptable.  The core library is focused on the view layer only and is easy to pick up and integrate with other libraries or existing projects.  On the other hand, Vue is also perfectly capable of powering sophisticated Single-Page Applications when used in combination with  modern tooling  and  supporting libraries . What is the best fit for Vue.js? As there are so so many Js Framework are there let me clear up what is the best fit for Vue.js Considering all the conceptual and technical aspects of Vue.js, you might question where it might fit the best. Besides its direct purpose, building one-page applications and working on web pages, it’s also suitable for a number of tasks. Dealing with prototypes (without too much skill) First and foremost, Vue.js was designed f...
Read more
Image
Fibonacci Series in C: Iterative vs Recursive Methods Learn how to compute the Fibonacci series in C using both iterative loops and recursive functions. When it comes to computing the Fibonacci series, there are various approaches to achieve the desired sequence. In this blog, we’ll explore two primary methods: iterative and recursive. Both have their unique advantages and can be utilized based on the specific requirements of your program. Let’s delve into the code and understand each method in detail. Iterative Fibonacci in C The iterative approach to calculating Fibonacci numbers uses loops and conditional statements. This method is straightforward and efficient in terms of both time and space complexity. Here’s a sample code snippet for the iterative method: # include <stdio.h> int main () { int n1 = 0 , n2 = 1 , n3, i, number, c = 0 ; printf ( "Fibonacci Series: Iterative" ); printf ( "\n\nEnter the number of elements: " ); scanf ( "%d...
Read more
Image
Unlocking Insertion Sort: A Practical Guide to Efficient Sorting with Dart Master the fundamentals of Insertion Sort with this detailed guide and Dart code examples, ideal for beginners and enthusiasts. Sorting algorithms are essential tools in a programmer’s toolkit, and Insertion Sort is a simple yet powerful method for sorting small datasets. In this blog, we’ll explore the mechanics of Insertion Sort, implement it in Dart, and highlight its key features and use cases. How Insertion Sort Works Insertion Sort is a comparison-based algorithm that builds the final sorted array one item at a time. It’s much like sorting a hand of playing cards: you pick each card and insert it into its correct position among the previously sorted cards. Here’s a step-by-step breakdown of Insertion Sort: Start from the second element: Assume the first element is already sorted. Pick the next element: Compare it with the elements in the sorted part of the array. Shift elements: Move all elements that are ...
Read more