Dijkstra’s Algorithm in C

9
19529

Dijkstra’s Shortest Path Algorithm is a popular algorithm for finding the shortest path between different nodes in a graph. It was proposed in 1956 by a computer scientist named Edsger Wybe Dijkstra. Often used in routing, this algorithm is implemented as a subroutine in other graph algorithm. In this post, I have included a pseudo code and source code for Dijkstra’s Algorithm in C along with a brief introduction to this algorithm.

Dijkstra’s algorithm finds the solution for the single source shortest path problems only when all the edge-weights are non-negative on a weighted, directed graph. In other words, the graph is weighted and directed with the first two integers being the number of vertices and edges that must be followed by pairs of vertices having an edge between them.

In the source code for Dijkstra’s algorithm in C, the inputs are asked as source, target and the weight of the path between two nodes. Before going through the source code for Dijkstra’s algorithm in C, here’s a look at the algorithm itself and a pseudo code based on the algorithm.

You can read more about Dijkstra’s algorithm by going to these links: Link 1. Link 2, and here are a couple of Youtube links you can watch if you don’t know much about this algorithm: Link 1. Link 2.

Dijkstra’s Algorithm to Find the Shortest Path:

Let’s fix a node as the initial node; this will be the node at which we are starting. Let the distance of node “Y” be the distance from the initial node to “Y”. Now, in Dijkstra’s algorithm, some initial distance values are assigned, and these values are improved step by step. The algorithm procedure is given below:

  1. A tentative distance value is assigned to every node; this value is set to zero for the initial node, and to infinity for all other nodes.
  2. All nodes unvisited are marked, and the initial node is set as current. An unvisited set ( a set of all the unvisited nodes) consisting of all the nodes is created.
  3. For the current/initial node, take into account all the unvisited nearby nodes, and calculate their tentative distances. Make a comparison of the current assigned value and the newly calculated tentative distance; assign the smaller value. For example: if the current/initial node X was marked with a distance of 4, and the edge connecting it with a nearby neighbor node Y has length 1, then the distance through X to Y will be 4 + 1 = 5. If Y was previously assigned a value greater than 5, then change it to 5. Otherwise, keep the value as it is.
  4. A visited node is never to be checked again. So, after finishing above steps with all the neighbors of the current node, make that node as visited and remove is from the unvisited set.
  5. Stop the algorithm if, when planning a route between two specific nodes, the destination node has been marked visited.
  6. Also, stop the algorithm if, when planning a complete traversal, the smallest tentative distance among the nodes in the unvisited set is infinity. This case is a result of no connection between the initial node and the remaining unvisited nodes.
  7. Find the unvisited node assigned with the smallest tentative distance value, and this will be the new “current mode”. Go back to step 3, and continue.

Below is an example which further illustrates the Dijkstra’s algorithm aforementioned. Consider a weighted graph as shown:

Dijkstra's Algorithm in C Weighted Graph
Weighted Graph

Here, a, b, c, d, e and f are nodes of the graph, and the number between them are the distances of the graph. Now, using Dijkstra’s algorithm we can find the shortest path between initial node a and the remaining vertices. For this, the adjacency matrix of the graph above is:

Dijkstra's Algorithm in C talble
Dijkstra’s Table

Pseudo Code for Dijkstra’s Algorithm:

Given above is a sample source code for Dijkstra’s algorithm, referred from Wikipedia. This exact pseudo may have not been used in writing the source code for Dijkstra’s algorithm in C, but it can be used as a reference for coding in any higher level programming language.

Source Code for Dijkstra’s Algorithm in C:

Copy and compile the source code above in Code::Blocks IDE. Compiling it on other platforms such as Turbo C may produce errors, and might require some modifications to the code. Go to this link to learn how routing algorithms work.

Also see,
Gaussian Filter Generation
Breadth First Search
Depth First Search

I hope the source code for Dijkstra’s algorithm in C is clear and easy to understand. If you have any queries or doubts regarding Dijkstra’s algorithm, it’s pseudo code or source code, mention them in the comments section below. You can find more C Tutorials here.

9 COMMENTS

  1. Nice explanation. Don’t you think you should start your loop with 0 instead of 1? Since you have 6 nodes for the given example, you could run your loop 6 times. Once again thanks for the code. We truly appreciate it.

  2. Hi,
    In the graph picture,you’ve missed writing distance between b-d. Plz correct that. And can u plz add some snapshot of program output? I tried entering your graph to your program during run,but it’s giving 0 as output. A snapshot of program is helpful. And I think in each program,at the start of program,if you add a printf statement stating how to use the program,will be helpful. Anyway,I found your site very very helpful. Keep it up!

  3. could you please help me with code for finding shortest path between source and destination pair, using priority vertices, through which graph is to be traversed to reach the destination.
    your help means alot to me , i have tried a lot fr dis, could find any correct result , please help me with this @pramesh pudasaini

    • How do I explain you the WHOLE source code? If you know nothing about Dijkstra’s Algorithm, please go through the post description first. The source code will be relatively easy to understand after that.

LEAVE A REPLY

Please enter your comment!
Please enter your name here