Finding The Shortest Path Between Two Points On A Graph Using Dijkstra’s Algorithm

Dijkstra’s Algorithm

Below are the fundamental steps that are taken by the Dijkstra’s algorithm to find the shortest path between two nodes:

  1. Find the start node and initialize its cost/distance to zero and set the cost/distance of all other nodes to infinity. We will call this the cost object. We will also initialize an empty array which we’ll call visited to keep track of nodes that we have analyzed. We will also need to keep track of the parent of each node so that we can track the shortest path taken. We’ll call this parentNodes.
  2. calculate the cost/distance between the start node and its children, updating the cost object of the child node with the new value if it’s lower. Alongside updating the cost object, we will update the parentNodes of this child node.
  3. Add the analyzed node to the visited array.
  4. Analyze the next lowest node (we can get that from the cost object) in a similar fashion to step 2. Repeat steps 2–4 until all nodes have been visited.
  5. Now we can determine the fastest path by examining the parentNodes object and trace the path from the finish node to the start node.

Implementation

To remind ourselves, this is our tree that we discussed above:

  1. calculate the distance from the start node to each of its neighbors, if the neighbor’s calculated cost is lower than what’s in the costs array, replace the value in the “costs” array with the new value. Also, point the parent of the child in the “parentNodes” to the current node being analyzed.
  2. After analyzing or neighboring nodes, add the current node to the “visited” array so we don’t analyze it again. Then find the closest child node that hasn’t been analyzed and repeat step 1 again until all nodes have been visited.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store