Dijkstra’s algorithm, finding the shortest path in JavaScript.

6 min readOct 27, 2019

Anyone who has ever used a smartphone to navigate somewhere has probably encountered situations where they are given a few different options of which route to take. What you might not realize is that all the work to find the fastest route took a lot of effort to find, maybe not for a computer but there’s a lot going on in the background. This process most likely requires or has one of the core concepts of one of the most important algorithms of our time which is Dijkstra’s algorithm.

Dijkstra’s algorithm is an algorithm for finding the shortest paths between nodes in a weighted graph. We’ll be implementing a JavaScript function to run our algorithm. What is a weighted graph you ask? A graph is an abstract data type used to model a set of connections.

On your phone, this graph would look like a map, but under the hood, it is a data structure called a weighted graph. The locations on the map are the nodes of the graph, the paths between them are the edges, and the time to get from any one node to the other is the weight of each edge.

The basic steps to finding the shortest path to the finish from start are the following.

Move to a node that we haven’t visited, choosing the fastest node to get to first.
At that node, check how long it will take us to get to each of its neighboring nodes. Add the neighbor’s weight to the time it took to get to the node we’re currently on. Keep in mind that we’re calculating the time to reach those nodes before we visit them.
Check whether that calculated time is faster than the previously known shortest time to get to that node. If it is faster, update our records to reflect the new shortest time. We’ll also add this node to our line of nodes to visit next. That line will be arranged in order of shortest calculated time to reach.

So we’re basically calculating the time it takes to reach one node to the next and picking the shortest path to the wanted node before we move on to the next node.

To start our graph let’s make an object, and we’ll use that as our argument for the main algorithm.

//Create the graph object
//Each key represents a node on the graph. Each key has an object for its value, which represents the immediate neighbors and the weight of reaching that neighbor. const graph = {
  start: {A: 5, B: 2},
      A: {C: 4, D: 2},
      B: {A: 8, D: 7},
      C: {D: 6, finish: 3},
      D: {finish: 1},
 finish: {}
};

So now that we created the graph object relative to the graph picture above, how is Dijkstra’s algorithm going to work with it? First, it needs to find the lowest node and then update the weight of the immediate neighbors of the node. Repeating those two steps until you’ve done this on every node. Finally return the lowest weight to reach the node, and the optimal path that we found to reach there.

In order to keep track of our nodes and their distances we will create another object called “weight” which is the distance from one node to the next. To begin we can say that we have a weight from start to A to be 5 and from start to B is 2. Since we don’t know where the path finishes we will set the finish weight to infinity for now. Here’s how it looks.

//Keep track of the lowest weight from one node to the next.
const weight = {
 A: 5,
 B: 2,
 finish: Infinity
};

We also need to keep track of the shortest path by making sure we keep track of the parent node each node or if there’s more than one possible parent we keep track of the one that leads to the lowest weight.

// Keep track of the lowest weight parent
const parents = {
  A: 'start', 
  B: 'start', 
  finish: null
};

If you’ve never heard of caching it means in order to save time we can also keep track of nodes that we have already visited. To keep track of that we’ll use an array data structure.

const visited = ["start", "A", "B"];

If you look at the graph again we cant to continue finding the lowest node and update the weight of the nodes children.

The lowest weight is node B(2) and it’s children are A and D. We add those to our weight object like so:

//weights
{ A: 5,
  B: 2,
  D: 9, //the total weight from start to D which is 2 + 7 = 9
  Finish: Infinity
};

Then we update the processed and parents data structures until we’ve processed all the nodes.

Let’s actually define a function that gives us the lowest weight node that hasn’t been processed given the weights and processed nodes.

const findLowestWeightNode = (weights, processed) => {
   const knownNodes = Object.keys(weights)
   
   const lowestWeightNode = knownNodes.reduce((lowest, node) => {
   if (lowest === null && !processed.includes(node)) {
    lowest = node;
    }
  if (weights[node] < weights[lowest] && !processed.includes(node)) {    
  lowest = node;
   }
  return lowest;
  }, null);
  
 return lowestWeightNode
};

Now let’s implement the main function, dijkstra, which will take our initial graph as a parameter. First we’ll make the weights, parents, and processed data structures.

const dijkstra = (graph) => {
   
// track lowest cost to reach each node  
const weights = Object.assign({finish: Infinity}, graph.start); 
  
// track paths  
const parents = {finish: null};  
for (let child in graph.start) {    
  parents[child] = 'start';  
 }
   
// track nodes that have already been processed  
const processed = [];//Next, we’ll set the initial value of the node being processed //using the lowestCostNode function. Then, we’ll begin a while loop, //which will continuously look for the cheapest node.let node = findLowestWeightNode(weights, processed);
   
while (node) {
//Get the weight of the current node
let weight = weights[node];//Get all the neighbors of current node
let children = graph[node]; //Loop through each of the children, and calculate the weight to reach that child node. We'll update the weight of that node in the weights object if it is lowest or the ONLY weight availablefor (let n in children) {   
    let newWeight = weight + children[n];     
     if (!weights[n] || weights[n] > newWeight) { 
      weights[n] = newWeight; 
      parents[n] = node;
        }
     } //push processed data into its data structure
 processed.push(node); // repeat until we processed all of our nodes.    
 node = findLowestWeightNode(weights, processed);
}
.... continued

All that seems like a lot and it is, BUT we’re almost done! Once the while loop is complete, we’ll have the lowest weight to reach the finish node. Now we set up our final function to get our optimal path. We do this by looking at our parents object that we made earlier.

...let optimalPath = ['finish'];let parent = parents.finish;while (parent) {
    optimalPath.unshift(parent);
    parent = parents[parent]; // add parent to start of path array
  }
  
  const results = {
    distance: weights.finish,
    path: optimalPath
  };

  return results;

}; //end of function

Our final results will look something like

{ distance: 8, path: [ 'start', 'A', 'D', 'finish']

Dijkstra’s algorithm, finding the shortest path in JavaScript.

Written by John Peña