Understanding Dijkstra’s algorithms

Dijkstra’s algorithm is used to find single shorted path between vertexes in a graph. For a given vertex, we can find the shortest path to all other vertexes. As we have to find a shorted path that means it a minimisation problem and minimisation problem is an optimisation problem. Optimisation problem can be solved by using greedy method.

This algorithm can be used on both directed as well as undirected graph.

Greedy method says that a problem is solved in stages, by taking one step at a time and considering one input at a time to achieve optimal solution.

Let’s take an example of this directed graph.

Directed graph with weighted edges

At each vertex, we check if there is any shorted path exist to the next vertex using current vertex, if yes then we update the distance for that vertex. This process is called Relaxation.

if (d[u] + c[u,v] < d[v]) then d[v] = d[u] + c[u,v]

// u is the current vertex
// v is the next vertex
// d is the distance
// c is the calculate distance from u to v.

// if the distance of next vertex is greater than the sum of 
// current vertex and the distance between current vertex to next vertex
// then update the next vertex with lower value

Time complexity for Dijkstra’s Algorithm is O(n*n)

Sudo code

- Take a starting node.
- Use a hashmap to keep track of vertex with their distance.
- Update the distance for all the direct connected nodes to the root node in the 
hashmap.
- Use an array to track all the vertexes that we have visited.
- Using the current hashmap, find the smallest neighbour and start exploring 
that vertex.
- check it neighbours and their distance, if current distance is less than
newly generated distance (for which we can use above formula) then update the next vertex.
- push the neighbours to visitedVertex array.
- Repeat the process until we have no closest neighbour to explore.

Let’s jump into the working of shorted path finding using Dijkstra’s algorithm by taking reference of our directed graph.

First, let’s create a adjacency list for our directed graph with the weight for each connected edge. That will look like :

const adjacencyList = {
  a: { b: 10, c: 5 }, // a is directing to b and c
  b: { d: 1 }, // b is directing to d 
  c: { b: 3, d: 9, e: 2 }, // c is directing to b,d and e
  d: {}, // d is not directing to any other vertex
  e: { a: 2 }, // e is directing to a
};

Let’s jump into the working of Dijkstra’s algorithm:

We’ll try to find a shorted path possible from a given node to the destination node using this algorithm;

• We need a function that can give us the closest vertex to process next from the current vertex.

/**
 * Function to fetch the closest neighbours vertex to process after current vertex
 * @param {*} currentNodeNeighbour , all neighbours nodes object
 * @param {*} visitedNodes, all the visited nodes for the graph
 * @returns {String} closest node
 */
const fetchClosestNode = (currentNodeNeighbour, visitedNodes) => {
  let closestNode = null;

  // iterating throught the list of neighbours of current node to fetch nearest one
  for (let node in currentNodeNeighbour) {
    // checking if the current node is the closest or not and also checking if that node is visited before or not
    if (
      (!closestNode ||
        currentNodeNeighbour[node] < currentNodeNeighbour[closestNode]) &&
      !visitedNodes.includes(node)
    ) {
      closestNode = node;
    }
  }
  return closestNode;
};

In the above code, we are checking the closest node from the neighbours of a node and also checking that node is not being visited before.

Let’s see the code for dijkstra’s shorted path finding algorithm and then we go through it line by line to understand it better.

/**
 * Function to fetch the shorted path that we can take to reach from start to end
 * @param {*} sourceNode , source node to start the journey
 * @param {*} endNode , end node to stop the journey
 * @param {*} graph , adjacency list representation of grah with weighted edges
 * @returns Shorted path weight
 */
const findShortedPathWithPathTracking = (sourceNode, endNode, graph) => {
  let distances = {};
  // setting the default distance for destination to Infinity as it will be always greater, easy to compare
  distances[endNode] = Infinity;

  // setting distance for starting node to 0
  distances[sourceNode] = 0;

  // setting the distance for connected nodes to the starting node
  distances = Object.assign(distances, graph[sourceNode]);

  // need to keep track of the visited nodes as well so that we don;t create a loop
  let visitedNodes = [];

  // fetch the nearest node
  let nearestNode = fetchClosestNode(distances, visitedNodes);
  // create a while loop to fetch the iterate over the neighous and calculate distance
  while (nearestNode) {
    const distance = distances[nearestNode];
    const neighbours = graph[nearestNode];
    // calculate the distance for the neighour node
    // iterate through neibhours
    for (let neibhour in neighbours) {
      // checking if neighbour is not starting vlaue so that we don;t keep in loop
      if (String(neibhour) === String(sourceNode)) {
        continue;
      } else {
        // calculating the new Distance for the neibhour node
        let newDistance = distance + neighbours[neibhour];
        // if new distance is less update it
        if (!distances[neibhour] || newDistance < distances[neibhour]) {
          distances[neibhour] = newDistance;
        }
      }
    }

    // mark the current node as visited
    visitedNodes.push(nearestNode);
    // calculating the next smallest node to visit from the unvisited nodes
    nearestNode = fetchClosestNode(distances, visitedNodes);
  }

  return distances[endNode];
};

Let’s run this algorithm to find distance from a to d:

console.log(findShortedPathWithPathTracking("a", "d", adjacencyList));

The result will be 9, as it will go through a, c, b and d.

Explanation:

• First we create a hashmap with name distances to keep track of distances for each vertex.
• Then we set the end node distance as Infinity as we have to find the shorted path to this node so let’s make it Infinity for now.
• Then we set the source node (starting point) distance as 0 because we are starting from that point, so no need to calculate distance.
• Now, we have a hashmap that has values for starting node, end Node and neighbours of current node. (As dijkstra says that, update the distance for nodes that are directly connected to the source node).
• Then we have initiated an array with name visitedNodesto keep track of nodes that we have visited , so no need to visit them again(to avoid loop).
• Then we have initialised a while loop that will run until we have no neighbours.
• Then in the while loop , we have variable distance to keep track of the distance for current node and neighbours to keep track of all the neighbours for the current node.
• Then we initialise a for in loop that will run for all our neighbours to check if they distance can be updated or not.
• At last , we push the current node to visited nodes as we have visited it and we start exploring the next nearest node.

For a practice you can do an enhancement on this algorithm by tracing the path for shorted distance along with the result.

Hope this make it easy for you to understand the working of dijkstra’s algorithm. If you have any questions do ask in the comment section.

Stay tuned for more to come, If you are new here, do checkout our Algorithms with Javascript blog, we are covering few of the most commonly used algorithms.

In the next blog, we’ll go through Diffie-Hellman key Exchange.