Dijkstra’s Algorithm in JavaScript

Photo by Zoran Borojevic on Unsplash

Dijkstra’s Algorithm is an algorithm to find the shortest path between vertices in a graph. It was created by Edsger W. Dijkstra, a Dutch computer scientist. Given a source vertex, the algorithm will find the shortest path between that vertex and all other vertices in the graph (returning infinity if there is no path between the source vertex and a given vertex). This is known as the shortest-path tree. It can be modified to find the shortest distance between the source vertex and a target vertex, simply by stopping once the shortest path is found for the target vertex.

Step by Step Example

Dijkstra’s Algorithm works on weighted, acyclic graphs. Acyclic means that there is no path from a given vertex back to itself, this means that for Dijkstra’s algorithm to work the graph must be directed. Weighted means that there is a value associated with each edge. These weights must be non-negative.

The steps are:

1. Find the vertex with the lowest weight.
2. Update the ‘distance’ of all of the adjacent vertices from that vertex (their own weight plus the distance of the node in step 1)
   a. If they already have a set distance only update it if the new distance is shorter.
3. Once we have done this for every vertex, each one should have the correct value of the shortest distance from itself to the source

Acyclic Weighted Graph

Take the above weighted graph, for example. Let’s assign A to be our source vertex.

Step 1

Let’s create a distances object, to represent the distances between each vertex and the source. At first we will assign the distance of each vertex, except our source, to infinity. We assign the distance of the source to 0.

source = A
distances = {
A: 0,
B: Infinity,
C: Infinity,
D: Infinity
}

Step 2

Find the vertex with the shortest distance from our distances object. That will be our source as it is 0 while the rest are infinity.

Update the distances of all of the adjacent vertices. From A, B and C are adjacent. We will update them to be the distance at A plus their weight.

distances = {
A: 0,
B: 0 + 3,
C: 0 + 2,
D: Infinity
}

Now we need to keep track of which vertices we’ve visited, so far that’s only A (even though we’ve updated the distances for B and C, they haven’t been ‘visited’ yet).

visited = {A}

Step 3

Find the vertex with the smallest distance, that hasn’t been visited yet. Currently that would be C, as A has a distance of 0 but has been visited, B has a distance of 3, and C has a distance of 2.

Update the distances of all of the adjacent vertices of C. That’s only D.

distances = {
A: 0,
B: 3,
C: 2,
D: 2 + 6
}

Add C to visited.

visited = {A, C}

Step 4

Find the vertex with the smallest distance that hasn’t been visited, again. That’s B.

Update the weights of the adjacent vertices, that’s only D. Since D already has a distance, we will only update it if the new distance is smaller.

distances = {
A: 0,
B: 3,
C: 2,
D: 8 > 3 + 2}

Since the current distance (8) is greater than the new distance (5), we will update it. This is why we initially set every distance to infinity, so that the first check to see if the current distance is greater will return true.

Now we add B to visited.

visited = {A, C, B}

Step 5

Now the only vertex that hasn’t been visited is D. D doesn’t have any adjacent vertices, so we have no distances to update.

We have gotten a distance for every vertex in the graph. Our distances object looks like: {A: 0, B: 3, C: 2, D: 5}. This is our shortest-path tree, that is the distance between A and every other node in the graph. Now we are ready to actually code Dijkstra’s algorithm.

Code

To start out, I am going to put all of this code in a Graph class, and an instance of a Graph will be able to form Dijkstra’s algorithm on itself.

The class constructor:

All of the code will go inside this class constructor. A Graph instance will need an array to keep track of its vertices, and an object to quickly look up the adjacency list of each vertex.

We need to be able to add vertices and edges.

addVertex adds a vertex to the array of vertices. It also assigns it its own adjacency list in the adjacency list object.

addEdge takes in two vertices, and creates an edge from the first to the second with the given weight.

changeWeight will change the weight on the edge from vertex1 to vertex2.

Now that we can create a simple graph, we can work on Djikstra’s algorithm.

To start we need an object to keep track of our distances, and a set to keep track of which vertices we’ve visited. I’ve added an object parents in which the key will be a given vertex, and the value will be which vertex leads to it in the shortest path.

From lines 5 to 12 we will set the distance of each vertex in the vertex object to Infinity, unless it is the source, then we will set it to 0. This is like step 1 in our step by step example. We also set the parent of each vertex to null.

On line 14 we are setting currVertex to the vertex with the minimum distance (I will explain the vertexWithMinDistance method after, just know it grabs the vertex that hasn’t been visited with the smallest distance). currVertex will be set to source originally as its distance will be 0.

Inside of our while loop, we get the distance of currVertex. We get all of the adjacent vertices by accessing the adjacency list for that vertex, we assign them to a variable called neighbors. We then iterate through every neighbor. We see calculate the distance of currVertex plus the weight of each neighbor and if it is less than the current distance of the neighbor we update the distance of that vertex in the distances object.

Once we’ve updated the distances of each neighbor we will add our currVertex to the visited set. We then assign currVertex to the vertex that hasn’t been visited, with the shortest distance.

We will repeat this process until every vertex is in the visited set. After that the distances object should contain the shortest distance between the source vertex and every other vertex in the graph. We will console.log the distances object and the parents object, however we could just as simply return them if we needed to work with that data.

Let’s look at the vertexWithMinDistance method now.

So we set minDistance to Infinity, and minVertex to null. We iterate through all of the vertices in the distances object. We get the distance of that vertex, if the distance is less than minDistance and it hasn’t been visited, we reassign minDistance and minVertex accordingly. At the end we return minVertex. If we have visited all the vertices it will return null.

Testing the Code

Time to see if Dijkstra’s algorithm is coded correctly.

That code creates a version of the graph we used in our step by step example. You can see all of the distances are correct, and if you look at the parent object, D has a parent of B, which has a parent of A, which is our source node. This is the correct path, though backwards. A to B to D is our shortest path from A to D.

In Conclusion…

Dijkstra’s algorithm is quite simple, but powerful. Dijkstra himself said that it only took him 20 minutes to come up with this algorithm! There are other shortest path finding algorithms, that perhaps I will look at next. Such as the Bellman-Ford Algorithm, Floyd-Warshall Algorithm, and Johnson’s Algorithm. I think that Dijkstra’s algorithm is a good first look at path finding in a weighted graph, as the steps are fairly simple and make sense. The code in this blog can be found in this GitHub repository.