Dijkstra Algorithm C Program with Step by Step Guide

By the time you finish reading this blog, you'll have a solid grasp of how Dijkstra’s Algorithm operates, where it’s applied, and how to put it into practice with arrays and loops. This guide is perfect for students, developers, and anyone eager to learn about data structures and algorithms.

What is Dijkstra’s Algorithm?

• 

  Ms. Sonal / 9 days
• 10
• 6 min read

Dijkstra’s Algorithm is a greedy algorithm designed to find the shortest distance from a starting node to all other nodes in a graph. For it to function correctly, the graph must have non-negative weights. This algorithm was created by the Dutch computer scientist Edsger W. Dijkstra back in 1956, and it continues to be one of the most significant graph algorithms today.

Key Features of Dijkstra’s Algorithm:

- It only works with graphs that have non-negative edge weights.

- It employs a greedy strategy to select the nearest unvisited vertex.

- It guarantees the shortest path from the source to every other vertex in the graph.

Applications of Dijkstra's Algorithm

Understanding where Dijkstra’s Algorithm is used can help you appreciate its importance in real-world situations. Here are some common applications:

- GPS Navigation Systems – It calculates the shortest driving route between two points.

- Network Routing Protocols – Used in protocols like OSPF (Open Shortest Path First) to find efficient routing paths.

- Social Media Platforms – It helps determine the shortest degree of separation between two users.

- Flight Booking Systems – It identifies the shortest and most cost-effective route between two cities.

- Video Games – It’s utilized in AI pathfinding for character navigation.

Step-by-Step Working of Dijkstra's Algorithm

Before we dive into the code, it's important to grasp how Dijkstra’s Algorithm operates, step by step. Imagine a weighted graph where all weights are non-negative.

Step 1 – Initialization

Start by setting the distance of the source node to 0, while all other nodes are set to infinity. Don’t forget to mark all nodes as unvisited.

Step 2 – Select the Nearest Node

From the unvisited nodes, choose the one with the smallest distance value. This will be your current node.

Step 3 – Update Neighboring Nodes

For each neighbor of the current node, calculate the new tentative distance. If this new distance is less than the current one, update it accordingly.

Step 4 – Mark as Visited

After updating all neighbors, mark the current node as visited.

Step 5 – Repeat

Keep repeating this process until every node has been visited or until you find the shortest path to your destination.

C Program for Dijkstra's Algorithm

Now, let’s put Dijkstra’s Algorithm into action using the C programming language. The following C program represents a graph with an adjacency matrix and follows the logic we just discussed.

Complete Code:

#include 
#define INFINITY 9999
#define MAX 10
 
void dijkstra(int G[MAX][MAX], int n, int startnode);
 
int main() {
	int G[MAX][MAX], i, j, n, u;
 
    printf("Enter number of vertices: ");
    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);
 
	dijkstra(G, n, u);
 
	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) {
            printf("\nDistance from node %d to %d: %d", startnode, i, distance[i]);
            printf("\nPath: %d", i);
 
        	j = i;
        	do {
                j = pred[j];
                printf(" <- %d", j); } while (j !="startnode);" < pre>
                    

Sample Input and Output

Input

Enter number of vertices: 5
 
Enter the adjacency matrix:
 
0 10 0 30 100
0 0 50 0 0
0 0 0 0 10
0 0 20 0 60
0 0 0 0 0
 
Enter the starting node: 0
                        

Output

Distance from node 0 to 1: 10

Path: 1<- 0< p>

Distance from node 0 to 2: 50

Path: 2<- 3 <- 0< p>

Distance from node 0 to 3: 30

Path: 3<- 0< p>

Distance from node 0 to 4: 60

Path: 4<- 2 3 <- 0< p>

Dry Run (Explanation of Execution)

Let’s walk through a dry run of the algorithm using the input provided:

1. We kick things off at node 0, setting its distance to 0 while marking all other nodes as INFINITY.

2. From node 0, we can reach nodes 1, 3, and 4, so we update their distances accordingly.

3. Next, we head to the nearest unvisited node, which is node 1, and continue this process.

4. As we go, we update the paths and keep track of the predecessors.

5. In the end, we backtrack to reveal the shortest path from the source.

Benefits of Dijkstra's Algorithm

- Ensures the shortest path from the source to every node

- Works efficiently with graphs that have non-negative edge weights

- Easy to implement using arrays

- Scales well for medium-sized graphs

Limitations of Dijkstra's Algorithm

- Struggles with negative edge weights

- Performance can drop in dense graphs

- Not very efficient for large-scale graphs unless you optimize with a priority queue

Related Course

If you're eager to dive deeper into graph algorithms and want to build a solid foundation in data structures and C programming, you should definitely check out the Data Structures Course in Noida offered by Uncodemy.

This course covers a wide range of topics, including graph theory, shortest path algorithms, trees, recursion, dynamic programming, and much more, all while providing hands-on training and support for job placements.

Conclusion

Dijkstra's Algorithm is an incredibly effective method for tackling shortest path problems in graphs that have non-negative weights. Implementing it in C gives you a clear and organized way to grasp how graph traversal and cost minimization work in tandem.

Whether you're preparing for interviews, engaging in competitive programming, or pursuing academic goals, getting a handle on Dijkstra’s Algorithm is crucial. Start practicing with various types of graphs and play around with the logic to deepen your understanding.

To further enhance your skills in C programming and data structures, consider enrolling in the Data Structures Course in Noida at Uncodemy and lay a strong groundwork in algorithmic thinking.

To dive into linked lists and other key topics with hands-on guidance, enroll in the Data Structures Course in Noida offered by Uncodemy.

Frequently Asked Questions

Q1. Can Dijkstra’s Algorithm be applied to graphs with negative weights?

Answer: No, Dijkstra’s Algorithm doesn’t handle negative edge weights properly. If you’re dealing with such graphs, the Bellman-Ford Algorithm is a better choice.

Q2. What is the time complexity of Dijkstra’s Algorithm?

Answer: The time complexity varies based on how it’s implemented. If you use arrays, it’s O(V^2). However, if you opt for a priority queue, you can bring it down to O((V + E) log V).

Q3. Is Dijkstra’s Algorithm applicable for undirected graphs?

Answer: Absolutely! It works for both directed and undirected graphs, as long as the edge weights are non-negative.

Q4. What are the data structures used in the implementation?

Answer: Typically, arrays are used to keep track of distances, visited nodes, and predecessors. For improved performance, a priority queue (min-heap) is often utilized.

Q5. Can we use Dijkstra’s Algorithm to find the shortest path between any two specific nodes?

Answer: Yes, you can! While it calculates the shortest distance from a source node to all other nodes, you can easily extract the shortest path to a specific destination from the results.

Q6. What is the space complexity of the algorithm?

Answer: The space complexity is O(V^2) when using adjacency matrices and O(V + E) for adjacency lists with a min-heap.