Dijkstra’s algorithm was conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959. It is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge path costs, producing a shortest path tree. This algorithm is often used in routing and as a subroutine in other graph algorithms. In this post, we will use this algorithm to finding the shortest (or cheapest) path for a car travelling from one city to another city by using given roads. This algorithm can also be called a Satellite Navigation System that can show drivers which way they should better go. You can download the source code of this software at the bottom of this page.


Let the node at which we are starting be called the initial node. Let the distance of node Y be the distance from the initial node to Y. Dijkstra’s algorithm will assign some initial distance values and will try to improve them step by step.

  1. Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes.
  2. Mark all nodes unvisited. Set the initial node as current. Create a set of the unvisited nodes called the unvisited set consisting of all the nodes except the initial node.
  3. For the current node, consider all of its unvisited neighbors and calculate their tentative distances. For example, if the current node A is marked with a tentative distance of 6, and the edge connecting it with a neighbor B has length 2, then the distance to B (through A) will be 6+2=8. If this distance is less than the previously recorded tentative distance of B, then overwrite that distance. Even though a neighbor has been examined, it is not marked as “visited” at this time, and it remains in the unvisited set.
  4. When we are done considering all of the neighbors of the current node, mark the current node as visited and remove it from the unvisited set. A visited node will never be checked again; its distance recorded now is final and minimal.
  5. If the destination node has been marked visited (when planning a route between two specific nodes) or if the smallest tentative distance among the nodes in the unvisited set is infinity (when planning a complete traversal), then stop. The algorithm has finished.
  6. Set the unvisited node marked with the smallest tentative distance as the next “current node” and go back to step 3.

Algorithm Constraints

  • Graph in Grid Form
  • Total No of Vertices/Nodes: 50
  • Nodes numbering from 0-49
  • No of Rows = 5
  • No of Columns = 10
  • Nodes in Each Row = 10
  • Nodes in Each Column = 5
  • Weights are predefined between each vertices/nodes
  • Initially Nodes color is black
  • Initially lines color is white
  • After running the algorithm visited nodes are represented by blue color and visited paths are represented by light green color.

Running Algorithm

As described above, this algorithm can be used to find the shortest (or cheapest) path for a car from one city to another by using given roads. So consider following graph for this example. Suppose each node represents a town and path between towns (nodes) represent the roads. Weight associated with path (roads) represents the cost of travelling through that road.

Now you can specify any of the town as source town and destination town. Your goal is to find the shortest path from source to destination. Suppose we enter,

Source Node = 0

Destination Node = 25

After giving source and destination nodes this algorithm will generate the shortest path and show it on console window.

This algorithm can also be called a “Satellite Navigation System” that shows to drivers which way they should better go.

Download Source code for graphical path finding system.

Tagged with: C/C++ languageObject OrientedSource Code

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>


Looking for something?

Use the form below to search the site:

Still not finding what you're looking for? Drop a comment on a post or contact us so we can take care of it!

Related News Feeds

Set your Twitter account name in your settings to use the TwitterBar Section.