In the previous post, I have covered how to Find all paths in a graph adopting a breadth first search implementation. I had additionally added a method to filter out all the paths and return the shortest one from a starting to a destination node. That works but it’s not the most efficient way to calculate the shortest path in a graph. In this post I will use the same sample graph to implement the Dijkstra algorithm to more efficiently find the shortest path.

Here again is what the graph looks like:

The idea is to store all nodes distances from the starting node as infinity into a distanceTable. I will then start exploring the graph edges from the starting node and for each edge, I will store its distance from the starting node into the distanceTable overwriting the distance anytime its distance cost is shorter than before. I will then repeat this action choosing to explore the unvisited node with the shortest distance from the starting node until all nodes have been visited.

At the end of the iteration I will have a table containing all the nodes from the graph with their relative shortest distance from the starting node.

In the previous implementation I used a queue to keep track of the probable paths. For this implementation I will use a Priority Queue. Here is my implementation of the priority queue in typescript. The first thing I need is to define the element that will be stored in the Priority Queue.

The class above has a generic element T as element value and a priority number.

The methods to check out here are enqueue and dequeue. Enqueue adds a priority element to the queue making sure that the underlying elements array is ordered with the element with the highest priority (the lowest priority number) first. Dequeue will remove and return the first element in the array (which is the one with the highest priority).
Now that I have sorted out my priority queue implementation I can focus on implementing the Dijkstra algorithm.

The graph class has and adjacencyList map that is used to represents the nodes and their edges. Here is my implementation of Dijkstra:

Here is a unit test I wrote before hand to verify the correctness of the implementation:

The complete codebase for this implementation can be found in the nodejs-series repository.